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

1
2
3
4
5
6
7
8

Input: intervals = [[0, 3], [2, 6], [3, 4], [6, 9]]
Output: [3, 6]
Explanation: 
- The set [3, 6] covers all intervals. 
- Interval [0, 3] is covered by 3.
- Interval [2, 6] is covered by 3 and 6.
- Interval [3, 4] is covered by 3.
- Interval [6, 9] is covered by 6.

Example 2

1
2
3

Input: [[1, 4], [4, 5], [7, 9], [9, 12]]
Output: [4, 9]
Explanation: Points 4 and 9 cover all intervals.
Similar Problems

Solution

Method 1 - Sorting by end

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

  1. Sort the intervals by their end points.
  2. Initialize a list to store the points that will cover the intervals.
  3. 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.
  4. Return the list of points covering all intervals.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
 public:
    vector<int> coverIntervals(vector<pair<int,int>> intervals) {
        sort(intervals.begin(), intervals.end(), [](const auto &a, const auto &b){
            return a.second < b.second;
        });
        vector<int> ans;
        int last = INT_MIN;
        for (auto &seg : intervals) {
            int s = seg.first, e = seg.second;
            if (last < s || last > e) {
                last = e;
                ans.push_back(last);
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

package main

import "sort"

func coverIntervals(intervals [][2]int) []int {
    sort.Slice(intervals, func(i, j int) bool { return intervals[i][1] < intervals[j][1] })
    ans := make([]int, 0)
    last := -1 << 60
    for _, seg := range intervals {
        s, e := seg[0], seg[1]
        if last < s || last > e {
            last = e
            ans = append(ans, last)
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public class Solution {
    public List<Integer> coverIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return new ArrayList<>();
        }

        // Sort intervals by their end points
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

        List<Integer> result = new ArrayList<>();
        int point = intervals[0][1];
        result.add(point);

        for (int[] interval : intervals) {
            if (interval[0] > point) {
                point = interval[1];
                result.add(point);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] intervals = {{0, 3}, {2, 6}, {3, 4}, {6, 9}};
        System.out.println(solution.coverIntervals(intervals)); // Output: [3, 6]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def coverIntervals(self, intervals: List[List[int]]) -> List[int]:
        if not intervals:
            return []

        # Sort intervals by their end points
        intervals.sort(key=lambda x: x[1])

        result = []
        point = intervals[0][1]
        result.append(point)

        for interval in intervals:
            if interval[0] > point:
                point = interval[1]
                result.append(point)

        return result

# For testing the solution
if __name__ == "__main__":
    solution = Solution()
    intervals = [[0, 3], [2, 6], [3, 4], [6, 9]]
    print(solution.coverIntervals(intervals))  # Output: [3, 6]

Complexity

  • ⏰ Time complexity: O(n log n)
    • Sorting: O(n log n), with n being the number of intervals.
    • Iteration: O(n) for iterating through the sorted intervals.
  • 🧺 Space complexity:  O(n) to store the result in the worst case (when intervals are disjoint), plus O(1) extra auxiliary space beyond input and output.