Cleaning Shifts

Interview

Time limit1sMemory limit128 MB

Summary

Cover shifts 1 through T with the fewest intervals, where each interval covers a contiguous range of shifts. Return the minimum number of intervals or -1.

Level: Medium6 of 10
Topics: Greedy, Sorting, Intervals, Two pointers
Solved: No attempts yet

Problem

Farmer John is assigning some of his $N$ cows ( $1 \le N \le 25{,}000$ ) to cleaning chores around the barn. He always wants at least one cow on cleaning duty, and has divided the day into $T$ shifts ( $1 \le T \le 1{,}000{,}000$ ), numbered from shift $1$ up to shift $T$ .

Each cow is only available for cleaning during a single interval of the day. Any cow selected for cleaning duty works for the entirety of her interval.

Help Farmer John assign cows to shifts so that (i) every shift is covered by at least one assigned cow, and (ii) the number of cows involved is as small as possible. If it is impossible to cover every shift, print $-1$ .

Input

Line $1$ : Two space-separated integers $N$ and $T$ .
Lines $2 \dots N+1$ : Each line contains the start and end times of the interval during which a cow can work. A cow works from the shift at its start time through the shift at its end time, inclusive.

Output

Line $1$ : The minimum number of cows Farmer John needs, or $-1$ if it is impossible to cover every shift.

Examples4

Example 1
Input
```
3 10
1 7
3 6
6 10
```
Expected output
```
2
```
Example 2
Input
```
1 5
1 5
```
Expected output
```
1
```
Example 3
Input
```
3 6
1 2
3 4
5 6
```
Expected output
```
3
```
Example 4
Input
```
1 1
1 1
```
Expected output
```
1
```