Set Intersection Size At Least Two — Problem & Solution
Set Intersection Size At Least Two solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Set Intersection Size At Least Two is a hard coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Sorting, Greedy
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Each intervals[i] = [start, end] stands for every integer from start to end, both included.
A set of integers nums is containing if every interval holds at least two of its integers.
Return the smallest possible size of a containing set.
Example 1
Input: intervals = [[1,3],[3,7],[8,9]]
Output: 5
Explanation: For example {2, 3, 4, 8, 9}: [1,3] holds 2 and 3, [3,7] holds 3 and 4, [8,9] holds 8 and 9.
Example 2
Input: intervals = [[1,3],[1,4],[2,5],[3,5]]
Output: 3
Explanation: {2, 3, 4} works.
Example 3
Input: intervals = [[1,2],[2,3],[2,4],[4,5]]
Output: 5
Constraints
1 <= intervals.length <= 3000intervals[i].length == 20 <= start < end <= 10^8
Hints for Set Intersection Size At Least Two
Hint 1
Process intervals by increasing
end. When an interval still needs points, the best points to add are the largest ones it contains — they reach furthest into later intervals.Hint 2
You only need to remember the two largest points chosen so far.
Hint 3
Sort by
endascending and, for equal ends, bystartdescending. Then each interval needs 0, 1 (addend) or 2 (addend - 1andend) new points depending on how many of the two largest chosen points it already contains.
How to solve Set Intersection Size At Least Two
A greedy that always picks points as far right as possible. Among intervals sorted by right end, the current one must get its missing points somewhere inside it, and choosing them at its right end keeps the most options open for the intervals that end later.
Approach
- Sort intervals by
endascending; break ties bystartdescending (narrower first). - Keep
a < b, the two largest points chosen so far (initially below every coordinate), andcount = 0. - For each
[s, e]: ifs <= a, both are inside — nothing to do. Else ifs <= b, onlybis inside: adde, soa = b,b = e,count += 1. Otherwise adde - 1ande:a = e - 1,b = e,count += 2. - Return
count.
Why it works
Every chosen point is at most the current interval's end, because earlier intervals end no later. So the chosen points inside [s, e] are exactly those >= s, and only the two largest matter: if the second largest a is >= s, the interval already holds two. When points must be added, any point in [s, e] works for this interval, and a larger one is in every later interval that a smaller one is in (later intervals end at or after e), so e and e - 1 dominate. The tie order guarantees that when s <= b < ... the new point e differs from b.
Complexity
- Time —
O(n log n) - Space —
O(1) beyond the sort
Pitfalls
- Without the start-descending tie break, two intervals with the same end can make the greedy add
etwice. - The two tracked points must be the two largest chosen, updated as a sliding pair.
- Intervals are inclusive, so
[3,7]contains 3: the shared point can serve both[1,3]and[3,7].
Reference solution
Python
from typing import List
def intersectionSizeTwo(intervals: List[List[int]]) -> int:
ivs = sorted(intervals, key=lambda iv: (iv[1], -iv[0]))
a, b = -1, -1 # the two largest chosen points, a < b
count = 0
for s, e in ivs:
if s <= a:
continue
if s <= b:
count += 1
a, b = b, e
else:
count += 2
a, b = e - 1, e
return countJava
public static int intersectionSizeTwo(int[][] intervals) {
int[][] ivs = intervals.clone();
Arrays.sort(ivs, (x, y) -> x[1] != y[1] ? Integer.compare(x[1], y[1]) : Integer.compare(y[0], x[0]));
int a = -1, b = -1; // the two largest chosen points, a < b
int count = 0;
for (int[] iv : ivs) {
int s = iv[0], e = iv[1];
if (s <= a) continue;
if (s <= b) {
count += 1;
a = b;
b = e;
} else {
count += 2;
a = e - 1;
b = e;
}
}
return count;
}C++
int intersectionSizeTwo(vector<vector<int>>& intervals) {
vector<vector<int>> ivs = intervals;
sort(ivs.begin(), ivs.end(), [](const vector<int>& x, const vector<int>& y) {
return x[1] != y[1] ? x[1] < y[1] : x[0] > y[0];
});
int a = -1, b = -1; // the two largest chosen points, a < b
int count = 0;
for (auto& iv : ivs) {
int s = iv[0], e = iv[1];
if (s <= a) continue;
if (s <= b) {
count += 1;
a = b;
b = e;
} else {
count += 2;
a = e - 1;
b = e;
}
}
return count;
}JavaScript
var intersectionSizeTwo = function(intervals) {
var ivs = intervals.slice().sort(function(x, y) { return x[1] - y[1] || y[0] - x[0]; });
var a = -1, b = -1; // the two largest chosen points, a < b
var count = 0;
for (var i = 0; i < ivs.length; i++) {
var s = ivs[i][0], e = ivs[i][1];
if (s <= a) continue;
if (s <= b) {
count += 1;
a = b;
b = e;
} else {
count += 2;
a = e - 1;
b = e;
}
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms