Meetings

Interview

Time limit1sMemory limit1024 MB

Summary
Each person occupies an interval [Si, Ei]; pair up people whose intervals overlap into disjoint pairs and maximize the number of pairs.
Level

Medium6 of 10

Topics
Greedy, Sorting, Intervals, Two pointers
Solved
No attempts yet

Problem

N people want to hold meetings. The i-th person stays in the meeting room from time Si to time Ei. If there is a moment when two people are in the meeting room at the same time, those two people can hold a meeting together. A person can be included in at most one meeting. You want to hold as many meetings as possible to improve work efficiency. Find the number of meetings that can be held.

Input

The first line gives N. (1 ≤ N ≤ 5 × 105)

Over N lines, Si and Ei are given, separated by a space. (For all i, 1 ≤ Si ≤ Ei ≤ 109)

Output

Print the maximum number of meetings that can be held.

Examples2

  1. Example 1

    Input
    5
1 5
2 4
3 3
5 6
999999999 1000000000
    Expected output
    2

  2. Example 2

    Input
    3
1 1
2 2
1 2
    Expected output
    1