AlgoInsight

DSA problem

Set Intersection Size At Least Two

HardGreedyPattern: Greedytop600AmazonGoogleMicrosoftBloombergApple

You are given a 2D integer array intervals where intervals[i] = [start_i, end_i] represents all the integers from start_i to end_i inclusively. A containing set is an array nums where each interval from intervals has at least two integers in nums. Return the minimum possible size of a containing set.

A brute-force solution would try every subset of integers up to some bound — totally infeasible because the interval endpoints can be as large as 10^8. The right structure to exploit is the classic interval scheduling intuition: pick integers greedily to "cover" as many future intervals as possible.

The pivotal sort is by ascending end-point, ties by descending start-point. Why? Sorting by end-point lets us settle intervals one at a time in the order they "close out", which is exactly the standard greedy schedule. Ties broken by descending start-point ensure that wider intervals come first so any picked points from a wider interval are equally usable for the narrower sibling.

Maintain the two most recent picks p1 < p2 (the candidate integers we have committed to so far). For each interval [s, e] in sorted order, count how many of p1, p2 lie in [s, e]. If both lie inside, no new picks needed. If only p2 lies inside, add one new pick: p1 = p2; p2 = e. If neither lies inside, add two new picks: p1 = e - 1; p2 = e. Pick the largest legal values (e and e - 1) so they have the best chance of also covering subsequent intervals. The size of nums is the running count, returned at the end.

Examples

Example 1
Input: intervals = [[1,3],[3,7],[8,9]]
Output: 5
Explanation: After sorting by end, we process [1,3], [3,7], [8,9]. Picks become {2,3} then add 6,7 making {2,3,6,7} then add 8,9 making {2,3,6,7,8,9} — wait, the optimal is 5: {2,3,7,8,9}? In fact the algorithm finishes with 5 picks because after [1,3] picks 2,3 and after [3,7] only 3 lies inside so add 7 yielding {2,3,7}, then [8,9] disjoint adds 8,9 for total 5.
Example 2
Input: intervals = [[1,3],[1,4],[2,5],[3,5]]
Output: 3
Explanation: After sort by end (ties by descending start): [1,3], [1,4] or [2,5] etc. Greedy picks {2,3} from [1,3], reuses both for [1,4] and [2,5] (only 3 fits the latter so add 5? no — both 2 and 3 are in [2,5]). Final picks of size 3 are sufficient (e.g., {2,3,5}).
Example 3
Input: intervals = [[1,2],[2,3],[2,4],[4,5]]
Output: 5
Explanation: Sorted by end-asc, start-desc: [1,2], [2,3], [2,4], [4,5]. Picks from [1,2]: {1,2}. [2,3] has only 2 inside, add 3 -> {1,2,3}. [2,4]: 2 and 3 inside (both), no add. [4,5] none inside, add 4,5 -> {1,2,3,4,5} of size 5.

Constraints

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

greedyarraysorting

Browse all DSA problems