Problem
Given a set of closed intervals, find the smallest set of numbers that covers all the intervals. If there are multiple smallest sets, return any of them.
OR
Let X be a set of n intervals on the real line. We say that a set of points P “stabs” X if every interval in X contains at least one point in P. Compute the smallest set of points that stabs X.
OR as specified in Coursera Data Structures and Algorithms Specialization, specifically from the Algorithmic Toolbox Course, Week 3- Greedy Algorithms:
You are responsible for collecting signatures from all tenants of a certain building. For each tenant, you know a period of time when he or she is at home. You would like to collect all signatures by visiting the building as few times as possible.
Given a set of n segments [[a0, b0], [a1, b1], . . . , [an-1, bn-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 [ai, bi]
there is a point x ∈ X such that ai ≤ x ≤ bi.
Examples
Example 1
|
|
Example 2
|
|
Solution
Method 1 - Sorting
To cover all intervals with the minimum number of points, we can focus on the end points of the intervals. By sorting intervals by their endpoints, we can efficiently determine the smallest set of points required to cover the intervals. Whenever a point from the sorted intervals is not covered, it can be added to the solution set.
Approach
- Sort the intervals by their end points.
- Initialize a list to store the points that will cover the intervals.
- Iterate through each sorted interval:
- If the current interval’s start is not covered by the last added point, add the current interval’s endpoint to the list.
- Return the list of points covering all intervals.
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n log n)
- Sorting:
O(n log n)
, withn
being the number of intervals. - Iteration:
O(n)
for iterating through the sorted intervals.
- Sorting:
- 🧺 Space complexity:
O(1)
for the list tracking points.