Skip to main content
Talentd

Set Intersection Size At Least Two - Solution & Explanation

HardArrayGreedySorting20 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

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.

  • For example, if 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 <= 3000
  • intervals[i].length == 2
  • 0 <= starti < endi <= 108

Approach Overview

Problem Overview: You are given a list of intervals [start, end]. The goal is to build a set of integers such that every interval contains at least two numbers from that set. The challenge is minimizing the total size of the chosen set while satisfying all intervals.

Approach 1: Brute Force Interval Coverage (Exponential / Inefficient)

A straightforward idea is to try selecting numbers for each interval and check whether the global set satisfies the requirement. For every interval, you could attempt combinations of numbers inside its range and verify whether all intervals contain at least two selected values. This effectively becomes a combinatorial search problem. The number of possibilities grows rapidly because each interval may contain many candidate numbers.

This approach repeatedly checks intersections between intervals and the current set, leading to extremely high computational cost. In the worst case the complexity becomes exponential with respect to the range size or number of intervals. Space complexity is also large because you must store candidate selections. This method only helps build intuition about the constraint that every interval must contribute at least two elements.

Approach 2: Greedy Approach with Sorting (O(n log n) time, O(1) space)

The efficient strategy relies on a greedy observation: intervals that end earlier should be satisfied first. Sort the intervals primarily by their end value and secondarily by start in descending order. Processing intervals in this order ensures that when you pick numbers near the end of an interval, those numbers have the highest chance of satisfying upcoming intervals as well.

Maintain the last two selected elements that currently cover intervals. For each interval, check how many of these chosen numbers fall inside it. If both already lie inside the interval, nothing needs to be added. If only one lies inside, add the interval's end value to guarantee two elements. If none lie inside, add end-1 and end. Choosing numbers as far right as possible maximizes reuse for future intervals.

This greedy decision works because later intervals have equal or larger end points after sorting. Numbers placed near the end will likely remain valid for multiple intervals. Sorting costs O(n log n), while the scan through intervals is O(n). Only a few variables track the latest chosen values, so the extra space is O(1).

The technique combines sorting with a greedy strategy and interval reasoning similar to problems involving arrays and scheduling.

Recommended for interviews: Interviewers expect the greedy sorting solution. Brute force demonstrates understanding of the constraint, but the key signal of strong problem‑solving is recognizing that placing elements near interval ends maximizes reuse across intervals. The optimal solution runs in O(n log n) time with constant extra space and handles large input sizes efficiently.

Approach 1: Greedy Approach with Sorting

This approach involves sorting the intervals based on their end values, and then using a greedy strategy to select integers such that each interval has at least two integers from this set. We iterate through the sorted intervals and keep track of two largest possible positions from the previous selection. If the current interval cannot contain these positions, we add new numbers strategically to ensure that the current interval is also covered.

The function intersectionSizeTwo first sorts the intervals by their end value to facilitate a greedy selection of numbers. It keeps track of two largest numbers selected so far, where largest and second_largest help ensure minimal addition of new numbers.
If the start of the current interval is beyond largest, two new numbers from the interval are added. If it's only beyond second_largest, then only one more number needs to be added.

Code

PythonC++JavaCC#JavaScript

Python

C++

Java

C

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting the intervals.
Space Complexity: O(1) as it uses constant space for the count and tracking variables.

Try this approach in the editor →

Approach 2: Sorting + Greedy

We want to select as few integer points as possible on the number line such that each interval contains at least two points. A classic and effective strategy is to sort intervals by their right endpoints and try to place selected points towards the right side of intervals, so that these points can cover more subsequent intervals.

First, sort all intervals by the following rules:

  1. Sort by right endpoint in ascending order;
  2. If right endpoints are equal, sort by left endpoint in descending order.

The reason for this sorting is: intervals with smaller right endpoints have less "operational space" and should be satisfied first; when right endpoints are equal, intervals with larger left endpoints are narrower and should be prioritized.

Next, we use two variables s and e to record the second-to-last point and last point that are common to all currently processed intervals. Initially, s = e = -1, indicating that no points have been placed yet.

Then we process the sorted intervals [a, b] one by one, and discuss three cases based on their relationship with {s, e}:

  1. If a leq s: The current interval already contains both points s and e, so no additional points are needed.

  2. If s < a leq e: The current interval only contains one point (i.e., e), and needs one more point. To make the new point most helpful for subsequent intervals, we choose the rightmost point b in the interval. Update ans = ans + 1, and set the new two points to {e, b}.

  3. If a > e: The current interval does not contain either of the existing two points, so two points need to be added. The optimal choice is to place {b - 1, b} at the rightmost side of the interval. Update ans = ans + 2, and set the new two points to {b - 1, b}.

Finally, return the total number of points placed, ans.

The time complexity is O(n times log n) and the space complexity is O(log n), where n is the number of intervals.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach with Sorting

Time Complexity: O(n log n) due to sorting the intervals.
Space Complexity: O(1) as it uses constant space for the count and tracking variables.

Sorting + Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Interval CoverageExponentialHighConceptual understanding or very small inputs
Greedy Approach with SortingO(n log n)O(1)Optimal solution for large inputs; standard interview approach

Video Solution

Set Intersection Size At Least Two - Leetcode 757 - Python • NeetCodeIO • 8,637 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Set Intersection Size At Least Two easy or hard?
Set Intersection Size At Least Two is classified as a Hard problem because the greedy insight is not immediately obvious. Many initial attempts lead to brute force or dynamic programming ideas. Recognizing that placing numbers near interval ends maximizes reuse across future intervals is the key difficulty.
Set Intersection Size At Least Two Python/Java solution
The standard implementation sorts intervals by end value and iterates through them while maintaining the last two chosen elements. When coverage is insufficient, new numbers such as end-1 and end are inserted into the solution set. This logic translates directly across Python, Java, C++, C#, C, and JavaScript.
How to solve Set Intersection Size At Least Two in O(n)?
The core interval processing step is O(n), but sorting the intervals requires O(n log n). After sorting by end position, iterate once through the intervals while tracking the last two selected numbers. Depending on how many of them fall inside the current interval, add zero, one, or two new numbers near the interval's end.
What is the best approach for Set Intersection Size At Least Two?
The optimal solution uses a greedy strategy combined with sorting. Intervals are sorted by their ending point, then processed sequentially while maintaining the last two selected numbers that cover previous intervals. When an interval is not fully covered, numbers near its end are added. This approach runs in O(n log n) time due to sorting and O(1) extra space.
Is Set Intersection Size At Least Two asked at Google/Amazon/Meta?
This problem reflects common interview themes used by companies like Google, Amazon, and Meta, especially around greedy algorithms and interval scheduling. Variants involving interval coverage, minimal selections, or scheduling with constraints appear frequently in senior-level algorithm interviews.
What data structure is used in Set Intersection Size At Least Two?
The solution primarily uses arrays for storing intervals and relies on sorting. Instead of complex structures, the algorithm tracks only the last two selected integers with simple variables. The main technique is greedy interval processing rather than advanced data structures.
What is the time complexity of Set Intersection Size At Least Two?
The optimal algorithm runs in O(n log n) time because the intervals must be sorted by their end values. After sorting, a single linear pass determines whether new numbers must be added to the set. The space complexity is O(1) since only a few variables track the most recently chosen elements.

Ready to solve this problem?

Practice Set Intersection Size At Least Two with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays