This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

An integer interval `[a, b]`

(for integers `a < b`

) is a set of all consecutive integers from `a`

to `b`

, including `a`

and `b`

.

Find the minimum size of a set S such that for every integer interval A in `intervals`

, the intersection of S with A has size at least 2.

**Example 1:**

Input:intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]Output:3Explanation:Consider the set S = {2, 3, 4}. For each interval, there are at least 2 elements from S in the interval. Also, there isn't a smaller size set that fulfills the above condition. Thus, we output the size of this set, which is 3.

**Example 2:**

Input:intervals = [[1, 2], [2, 3], [2, 4], [4, 5]]Output:5Explanation:An example of a minimum sized set is {1, 2, 3, 4, 5}.

**Note:**

`intervals`

will have length in range`[1, 3000]`

.`intervals[i]`

will have length`2`

, representing some integer interval.`intervals[i][j]`

will be an integer in`[0, 10^8]`

.

b'

\n#### Approach #1: Greedy [Accepted]

\n

\n

'
\n\n

\n**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.

\n**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:\n`[[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**

- \n
- \n
Time Complexity: , where is the length of

\n`intervals`

. \n - \n
Space Complexity: .

\n \n

\n

Analysis written by: @awice.

\n