Problem B
Interval Scheduling
![/problems/intervalscheduling/file/statement/en/img-0001.png](/problems/intervalscheduling/file/statement/en/img-0001.png)
Consider a set of $n$ intervals $I_1,\ldots , I_ n$, each given as an integer tuple $(s_ i, f_ i)$ with $s_ i<f_ i$, such that the $i$th interval starts at $s_ i$ and ends at $f_ i$. We want to determine the maximum number of nonoverlapping intervals. More formally, we want to determine the size of a largest subset $S\subseteq \{ 1,\ldots ,n\} $ such that for $i, j\in S$ with $i\neq j$ we have $f_ j \leq s_ i$ or $f_ i\leq s_ j$. Note that the intervals $[1,2]$ and $[2,3]$ are not considered to be overlapping.
Input
The first line of input consists of an integer $n\in \{ 1,\ldots , 10^5\} $, the number of intervals. Each of the following $n$ lines consists of two space-separated integers $s$ and $f$, indicating an interval starting at $s$ and ending at $f$, with $0\leq s<f\leq 10^9$.
Output
Output a single integer, the largest number of nonoverlapping intervals.
Sample Input 1 | Sample Output 1 |
---|---|
3 1 4 2 8 5 9 |
2 |
Sample Input 2 | Sample Output 2 |
---|---|
8 0 6 1 4 3 5 3 8 4 7 5 9 6 10 8 11 |
3 |