Segments
Limits: 2 sec., 256 MiB
This statement was translated automatically from Ukrainian.
Given a set \(S\) of \(n\) segments. The segments lie on a coordinate line and the \(i\)-th segment occupies the interval \([a_i, b_i]\).
By definition, an interval \([l_1, r_1]\) contains an interval \([l_2, r_2]\) if \(l_1 \le l_2 < r_2 \le r_1\) holds.
In this problem, you need to find the size of the largest subset of \(S\) in which no segment contains another.
Input
The first line contains a single integer \(n\) — the number of segments.
The following \(n\) lines contain two integers \(a_i\) and \(b_i\) each — the coordinates of the beginning and the end of the \(i\)-th segment.
Output
Print a single integer in the only line — the maximum size of the subset.
Constraints
40% of tests: \(1 \le n \le 100\),
60% of tests: \(100 \le n \le 10^5\),
\(1 \le a_i < b_i \le 10^9, i = 1..n\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 4 2 5 1 4 1 6 3 8 | 3 |
| Input (stdin) | Output (stdout) |
|---|---|
| 5 5 8 3 7 4 10 12 15 1 7 | 3 |
Notes
In the first test, you can get the answer 3 by choosing the first, second, and fourth segments.
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|