-
Notifications
You must be signed in to change notification settings - Fork 5
/
covering_segments.py
40 lines (32 loc) · 1.15 KB
/
covering_segments.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
"""
Given a set of n segments {[a(0) ,b(0) ],[a(1) ,b(1) ],…,[a(n)−1 ,b(n)−1 ]} with integer coordinates on a line,
find the minimum number m of points such that each segment contains at least one point.
"""
from collections import namedtuple
def covering_segments(segments: [tuple]) -> list:
"""
Function for finding minimum number of points that each segment contains
Args:
segments: list of tuples with start and end point coordinates
Returns:
list of points where segments are crossing
Examples:
>>> covering_segments([(4, 7), (1, 3), (2, 5), (5, 6)])
[3, 6]
"""
segment = namedtuple('Segment', 'start end')
points = []
named_segments = list(map(lambda i: segment(i[0], i[1]), segments))
named_segments.sort()
end_point = named_segments[0].end
point = end_point
for segment in named_segments:
if segment.start > end_point:
points.append(point)
end_point = segment.end
point = end_point
if segment.end < end_point:
end_point = segment.end
point = end_point
points.append(point)
return points