banchan86
5/21/2017 - 4:12 AM

Greedy Algorithm to cover segments with minimum number of points. useful for organising groups of children for instance.

Greedy Algorithm to cover segments with minimum number of points. useful for organising groups of children for instance.

Covering_segments.py
content_copyfile_download
# Uses python3
import sys
from collections import namedtuple

Segment = namedtuple('Segment', 'start end')

def optimal_points(segments):
    points = []
    sorted_segments = sorted(segments, key=lambda x: x[1])
    max_point = -1
    for s in sorted_segments:
        if s.start>max_point:
            max_point = s.end
            points.append(s.end)
    return points

input = sys.stdin.read()
n, *data = map(int, 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=' ')