Approach #1: Greedy [Accepted]
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
We will try to extend this solution to the case when we want an intersection of size two.
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
S, when handling
[2, 3] we need to put
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, s+1) will be unused.
Time Complexity: , where is the length of
Space Complexity: .
Analysis written by: @awice.