Number Assignment

NumberAssingment.md

code

def calc(ns, g):
    ns.sort()  # sort list o(nlg(n))
    ds = []
    for i in range(len(ns)-1):  # o(n)
        ds.append(ns[i+1]-ns[i])
    ds.sort()
    while g > 1:
        ds.pop()  # pop the biggest one
        g = g - 1
    return sum(ds)  # o(n)


def test():
    testdata = [
        {'ns': [5, 2, 3, 10, 7, 2, 6, 8], 'g': 3},
        {'ns': [10, 1, 29, 15, 6], 'g': 5},
        {'ns': [105, 3, 27, 86], 'g': 1},
        {'ns': [37, 290, 15, 60, 4, 39, 2, 8, 275, 301], 'g': 2},
    ]
    for idx in range(len(testdata)):
        data = testdata[idx]
        print 'Case #%d: %d' % (idx+1, calc(data['ns'], data['g']))


if __name__ == '__main__':
    test()

result

Case #1: 4
Case #2: 0
Case #3: 102
Case #4: 84
[Finished in 0.1s]