Set Intersection Size At Least Two
Problem
Given a list of intervals, find the minimum size of a set such that every interval contains at least two integers from that set.
- 1 ≤ intervals.length ≤ 3000
- intervals[i].length == 2
- 0 ≤ starti < endi ≤ 10⁸
Example
intervals = [[1,3],[1,4],[2,5],[3,5]]3Think of this as efficiently 'pinning' tasks on a timeline. We need 2 pins per task. 1. The algorithm sorts intervals by End Time Ascending (and Start Time Descending for ties). Sorted order: `[[1,3], [1,4], [3,5], [2,5]]`. 2. Processing `[1,3]`: We have no pins. We need 2. The greedy choice is to place them as late as possible to maximize overlap with future tasks. We place pins at `2` and `3`. (Set: `{2, 3}`). 3. Processing `[1,4]`: Our pins `{2, 3}` are both inside. Requirement met. Do nothing. 4. Processing `[3,5]`: Only pin `3` is inside. We need 1 more. Place it at the very end, `5`. (Set: `{2, 3, 5}`). 5. Processing `[2,5]`: Pins `{3, 5}` are inside. Requirement met. Result: 3.
Approach
Straightforward Solution
A brute-force approach would attempt to generate all subsets of integers within the range of the intervals and check if they satisfy the '2-point' condition. Given the range can go up to 10^8, this is computationally impossible.
Core Observation
To minimize the total points used, every point added must serve the maximum number of future intervals. Since intervals are processed from left to right (based on end time), the optimal position for any new point is the rightmost possible position (the end of the current interval), as this extends its 'reach' furthest into subsequent intervals.
Path to Optimal
PreviewThe key recognition signals are 'intervals', 'minimum size', and 'overlap'. These indicate a Greedy approach based on sorting…
Full step-by-step walkthrough on Pro →
Optimal Approach
Preview1. Sort intervals by End Time Ascending…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(N log N)
Sorting the intervals takes O(N log N). The subsequent pass checks each interval exactly once, performing O(1) operations per check.
Space
O(1)
O(1) auxiliary space. We only track the last two points (`p1`, `p2`) and a counter. We do not need to store the full set of points to determine the answer.
Pattern Spotlight
Greedy Algorithms (Interval Sorting)
When greedy decisions on intervals depend on overlaps, sort by End Time to linearize the timeline. Crucially, if End Times match, sort by Start Time *Descending* to process the most restrictive (shortest) intervals first.
Solution
| 1 | class Solution: |
| 2 | def intersectionSizeTwo(self, intervals: List[List[int]]) -> int: |
| 3 | intervals.sort(key=lambda x: (x[1], -x[0])) |
| 4 | |
| 5 | p1, p2 = -1, -1 |
| 6 | count = 0 |
| 7 | |
| 8 | for start, end in intervals: |
| 9 | if p1 >= start and p2 >= start: |
| 10 | continue |
| 11 | |
| 12 | if p2 >= start: |
| 13 | count += 1 |
| 14 | p1 = p2 |
| 15 | p2 = end |
| 16 | else: |
| 17 | count += 2 |
| 18 | p1 = end - 1 |
| 19 | p2 = end |
| 20 | |
| 21 | return count |
Step-by-Step Solution
Sort Intervals by 'Earliest Finish, Latest Start'
| 3 | intervals.sort(key=lambda x: (x[1], -x[0])) |
Objective
To order the intervals such that we handle the most constrained deadlines first.
Key Insight
Sorting by End Time (`x[1]`) allows us to make a greedy decision that is locally optimal (satisfying the current interval) and globally optimal (extending furthest right). The secondary sort by Start Time Descending (`-x[0]`) is the critical fix for **nested intervals**: it ensures that if interval A is inside interval B and they end together, we process the *inner* (A) first. Satisfying the stricter inner interval automatically satisfies the outer one.
Interview Quick-Check
Core Logic
The sort key `(x[1], -x[0])` orders by deadline, while prioritizing shorter/stricter intervals when deadlines clash.
Common Pitfalls & Bugs
Forgetting the negative sign on `x[0]` will cause the algorithm to fail on nested intervals like `[1,5]` and `[2,5]`.
Initialize State Trackers
To initialize the variables that track the locations of the two most recently placed points.
Execute Greedy Coverage Strategy
To iterate through the sorted intervals and add the minimum number of points required to satisfy the 2-point overlap constraint.
Return Total Set Size
To return the accumulated count of points added.
3 more steps with full analysis available on Pro.
Line Analysis
This solution has 6 Critical lines interviewers watch for.
intervals.sort(key=lambda x: (x[1], -x[0]))Sort intervals by end time ascending, then start time descending.
This specific sort order is the engine of the solution; it linearizes the problem by deadline and handles nested intervals by processing the strictest constraint first.
p2 = endPlace the new point at the very end of the current interval.
This is the greedy choice that guarantees optimality; picking the rightmost possible point maximizes the chance of overlapping with the next interval.
p1 = end - 1Place the first new point at `end - 1`.
We pick `end - 1` instead of `start` because it is further right, offering better overlap potential while remaining distinct from `end`.
Full line-by-line criticality + rationale for all 15 lines available on Pro.
Test Your Understanding
Why is it sufficient to track only the last two points (`p1`, `p2`) instead of the entire set of chosen points?
See the answer with Pro.
Related Problems
Greedy Algorithms pattern
Don't just read it. Drill it.
Reconstruct Set Intersection Size At Least Two from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Set Intersection Size At Least Two drill