about summary refs log tree commit diff
path: root/scratch/facebook/merging-ranges.py
blob: 6da44572ee7ec26a392bd0975e67dace4e5d478d (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def merge(xs):
    xs.sort()
    result = xs[0:1]
    for a, b in xs[1:]:
        y, z = result[-1]
        if a <= z:
            result[-1] = (y, max(b, z))
        else:
            result.append((a, b))
    return result

inputs = [([(0,1),(3,5),(4,8),(10,12),(9,10)], [(0,1),(3,8),(9,12)]),
          ([(1,2),(2,3)], [(1,3)]),
          ([(1,5),(2,3)], [(1,5)]),
          ([(1,10),(2,6),(3,5),(7,9)], [(1,10)]),
          ]
for x, expected in inputs:
    result = merge(x)
    print(x)
    print(result)
    assert result == expected
    print("Success!")