Advertisement
jules0707

covering_segments

Jun 23rd, 2017
190
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.00 KB | None | 0 0
  1. # Uses python3
  2. import sys
  3. from collections import namedtuple
  4.  
  5. Segment = namedtuple('Segment', 'start end')
  6.  
  7.  
  8. def optimal_points(segments):
  9.     points = []
  10.     # we first sort segments by increasing right end point order
  11.     segments.sort(key=lambda segment: segment[1])
  12.     i = 0
  13.     while i <= len(segments) - 1:
  14.         # a safe move is to add the first right end point of the minimum segment to the list
  15.         end_point = segments[i].end
  16.         points.append(end_point)
  17.         i += 1
  18.         # we look for the next segment whose start point is not covered by the current end point
  19.         while i <= len(segments) - 1 and end_point >= segments[i].start:
  20.             i += 1
  21.     return points
  22.  
  23.  
  24. if __name__ == '__main__':
  25.     user_input = sys.stdin.read()
  26.     n, *data = map(int, user_input.split())
  27.     segments = list(map(lambda x: Segment(x[0], x[1]), zip(data[::2], data[1::2])))
  28.     points = optimal_points(segments)
  29.     print(len(points))
  30.     for p in points:
  31.         print(p, end=' ')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement