Approach #1: Greedy [Accepted]
Intuition
Let's try to solve a simpler problem: what is the answer when the set intersection size is at least one?
Sort the points. Take the last interval [s, e]
, which point on this interval will be in S
? Since every other interval has start point <= s
, it is strictly better to choose s
as the start. So we can repeatedly take s
in our set S
and remove all intervals containing s
.
We will try to extend this solution to the case when we want an intersection of size two.
Algorithm
For each interval, we will perform the algorithm described above, storing a todo
multiplicity which starts at 2
. As we identify points in S
, we will subtract from these multiplicities as appropriate.
One case that is important to handle is the following:
[[1, 2], [2, 3], [2, 4], [4, 5]]
. If we put 4, 5
in S
, then we put 2
in S
, when handling [2, 3]
we need to put 3
in S
, not 2
which was already put.
We can handle this case succinctly by sorting intervals [s, e]
by s
ascending, then e
descending. This makes it so that any interval encountered with the same s
has the lowest possible e
, and so it has the highest multiplicity. When at interval [s, e]
and choosing points to be included into S
, it will always be the case that the start of the interval (either s
or s, s+1
) will be unused.
Complexity Analysis

Time Complexity: , where is the length of
intervals
. 
Space Complexity: .
Analysis written by: @awice.