Problem Introduction
You are given a set of segments on a line and your goal is to mark as few points on a line as possible so that each segment contains at least one marked point.
Problem Description
Task.Given a set of n segments \(\{ [a_0, b_0], [a_1, b_1] \cdots [a_{n-1}, b_{n-1}] \}\) with integer coordinates on a line, find minimum number \(m\) of points such that each segment contains at least one point. That is, find a set of integers \(X\) of the minimum size such that for any segment \([a_i, b_i]\) there is a point \(x \in X\) such that \(a_i \leq x \leq b_i\).
Input Format.
The first line of input contains the number \(n\) of segments. Each of the following line contains the two integers \(a_i\) and \(b_i\)(separated by a space) defining the endpoints of the i-th segment.
Constraints.
$1 \leq n \leq 100; 0 \leq a_i \leq b_i \leq10^9; $ for all \(0 \leq i < n\).
Output Format.
Output the minimum number \(m\) of points on the first line and the integer coordinates of \(m\) points(separated by a space) on the second line. You can output the points in any orders. If there are many such sets of points, you can output any set. (It is not difficult to see that there always exists a set of points of the minimum size such that all the coordinates of the points are integers.)
Sample 1.
Input:
3
1 3
2 5
3 6
Output:
1
3
Sample 2.
Input:
4
4 7
1 3
2 5
5 6
Output:
2
3 6
Solution
# Uses python3
import sys
from collections import namedtuple
from operator import itemgetter
Segment = namedtuple('Segment', 'start end')
def optimal_points(segments):
points = []
endpoint = -1
segments = sorted(segments, key=itemgetter(1))
for segment in segments:
if endpoint < segment.start:
endpoint = segment.end
points.append(endpoint)
return points
if __name__ == '__main__':
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=' ')