forked from adnanaziz/EPIJudge
-
Notifications
You must be signed in to change notification settings - Fork 0
/
intervals_union.py
49 lines (36 loc) · 1.57 KB
/
intervals_union.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import collections
import functools
from test_framework import generic_test
from test_framework.test_utils import enable_executor_hook
Endpoint = collections.namedtuple('Endpoint', ('is_closed', 'val'))
Interval = collections.namedtuple('Interval', ('left', 'right'))
def union_of_intervals(intervals):
# Empty input.
if not intervals:
return []
# Sort intervals according to left endpoints of intervals.
intervals.sort(key=lambda i: (i.left.val, not i.left.is_closed))
result = [intervals[0]]
for i in intervals:
if intervals and (i.left.val < result[-1].right.val or
(i.left.val == result[-1].right.val and
(i.left.is_closed or result[-1].right.is_closed))):
if (i.right.val > result[-1].right.val or
(i.right.val == result[-1].right.val and i.right.is_closed)):
result[-1] = Interval(result[-1].left, i.right)
else:
result.append(i)
return result
@enable_executor_hook
def union_of_intervals_wrapper(executor, intervals):
intervals = [
Interval(Endpoint(x[1], x[0]), Endpoint(x[3], x[2])) for x in intervals
]
result = executor.run(functools.partial(union_of_intervals, intervals))
return [(i.left.val, i.left.is_closed, i.right.val, i.right.is_closed)
for i in result]
if __name__ == '__main__':
exit(
generic_test.generic_test_main("intervals_union.py",
"intervals_union.tsv",
union_of_intervals_wrapper))