Covering Segments by Points
This problem was taken from the Coursera Data Structures and Algorithms Specialization, specifically from the Algorithmic Toolbox Course, Week 3:Greedy Algorithms, that I’ve recently completed. If you are taking that course or plan to take that course, please don’t look ahead at the solution as it will be against the Honor Code and won’t do you any good.
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) ],…,[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. 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 ∈ X such that a(i) ≤ x ≤ b(i) .
Input Format. The first line of the input contains the number n of segments. Each of the following n lines contains two integers a(i) and b(i) (separated by a space) defining the coordinates of endpoints of the i-th segment.
Constraints. 1 ≤ n ≤ 100; 0 ≤ a(i) ≤ b(i) ≤ 10^9 for all 0 ≤ i < n.
Output Format. Output the minimum number m of points on the first line and the integer coordinates of m points (separated by spaces) on the second line. You can output the points in any order. If there are many such sets of points, you can output any set. (It is not difficult to see that there always exist a set of points of the minimum size such that all the coordinates of the points are integers.)
Time Limits. C: 1 sec, C++: 1 sec, Java: 1.5 sec, Python: 5 sec. C#: 1.5 sec, Haskell: 2 sec, JavaScript: 3 sec, Ruby: 3 sec, Scala: 3 sec.
Memory Limit. 512 Mb
Sample 1
Input:
3
1 3
2 5
3 6
Output:
1
3
Explanation:
In this sample, we have three segments: [1,3],[2,5],[3,6] (of length 2,3,3 respectively). All of them contain the point with coordinate 3: 1 ≤ 3 ≤ 3, 2 ≤ 3 ≤ 5, 3 ≤ 3 ≤ 6.
Sample 2
Input:
4
4 7
1 3
2 5
5 6
Output:
2
3 6
Explanation:
The second and the third segments contain the point with coordinate 3 while the first and the fourth segments contain the point with coordinate 6. All the four segments cannot be covered by a single point, since the segments [1,3] and [5,6] are disjoint.
What To Do
To design a greedy algorithm for this problem, consider a segment with the minimum right endpoint. What is a safe way to cover it by a point?
My Solution:
Hint:
The key is to sort the segments according to their end points.
If you can think of any other way to improve this algorithm or if you could point out something that you think I did wrong, you’re more than welcome to reach out to me by responding to this and pointing out the mistakes. If you like this solution, please hit the “Recommend” button below, it’ll mean a lot to me. Thanks.
