You are given a 2D integer array intervals where intervals[i] = [starti, endi] represents all the integers from starti to endi inclusively.
A containing set is an array nums where each interval from intervals has at least two integers in nums.
intervals = [[1,3], [3,7], [8,9]], then [1,2,4,7,8,9] and [2,3,4,8,9] are containing sets.Return the minimum possible size of a containing set.
Example 1:
Input: intervals = [[1,3],[3,7],[8,9]] Output: 5 Explanation: let nums = [2, 3, 4, 8, 9]. It can be shown that there cannot be any containing array of size 4.
Example 2:
Input: intervals = [[1,3],[1,4],[2,5],[3,5]] Output: 3 Explanation: let nums = [2, 3, 4]. It can be shown that there cannot be any containing array of size 2.
Example 3:
Input: intervals = [[1,2],[2,3],[2,4],[4,5]] Output: 5 Explanation: let nums = [1, 2, 3, 4, 5]. It can be shown that there cannot be any containing array of size 4.
Constraints:
1 <= intervals.length <= 3000intervals[i].length == 20 <= starti < endi <= 108#757 Set Intersection Size At Least Two is a classic greedy interval problem that requires constructing the smallest possible set of integers such that every interval contains at least two elements from the set. A key observation is that intervals should be processed in an order that makes greedy choices safe.
The common strategy is to sort the intervals by their ending value (and sometimes by starting value as a tie‑breaker). By processing intervals with smaller end points first, we ensure that selected elements can satisfy as many future intervals as possible. While iterating through the sorted intervals, we maintain the latest chosen elements and check how many of them already fall within the current interval.
If fewer than two elements intersect the interval, we greedily add new elements as close to the interval end as possible to maximize reuse for upcoming intervals. This approach avoids unnecessary additions and ensures minimal set size.
The algorithm relies on careful interval sorting and greedy selection, leading to efficient performance for large inputs.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy with Interval Sorting | O(n log n) | O(1) |
Ashish Pratap Singh
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems similar to #757 frequently appear in interviews at top tech companies. They test understanding of greedy strategies, interval sorting techniques, and the ability to reason about optimal choices under constraints.
The optimal approach uses a greedy strategy combined with sorting intervals by their end values. By always adding elements near the interval's end when necessary, the algorithm maximizes overlap with future intervals and minimizes the total number of elements chosen.
The solution mainly relies on arrays and careful tracking of the last selected elements. Since we only need to remember the most recently chosen values, complex data structures are usually unnecessary.
Sorting by end points allows the algorithm to satisfy intervals that finish earlier first. This greedy ordering ensures that newly added elements can potentially cover multiple upcoming intervals, reducing redundant selections.