Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # Uses python3
- import sys
- from collections import namedtuple
- Segment = namedtuple('Segment', 'start end')
- def optimal_points(segments):
- points = []
- # we first sort segments by increasing right end point order
- segments.sort(key=lambda segment: segment[1])
- i = 0
- while i <= len(segments) - 1:
- # a safe move is to add the first right end point of the minimum segment to the list
- end_point = segments[i].end
- points.append(end_point)
- i += 1
- # we look for the next segment whose start point is not covered by the current end point
- while i <= len(segments) - 1 and end_point >= segments[i].start:
- i += 1
- return points
- if __name__ == '__main__':
- user_input = sys.stdin.read()
- n, *data = map(int, user_input.split())
- segments = list(map(lambda x: Segment(x[0], x[1]), zip(data[::2], data[1::2])))
- points = optimal_points(segments)
- print(len(points))
- for p in points:
- print(p, end=' ')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement