Given N closed intervals [x_i, y_i], split them into the least number of groups such that all intervals in each group are pairwise non-overlapping (including endpoints). Output this minimum count.

Input Format

The first line contains an integer N, the number of intervals. The next N lines each contain two integers x_i and y_i, representing the endpoints of an interval.

Output Format

Output a integer, the minimum number of groups required.

Data Range

1 ≤ N ≤ 10^5 −10^9 ≤ x_i ≤ y_i ≤ 10^9

Input Example

3
-1 1
2 4
3 5

Output Example

2

---

Approach 1: Priority Queue (Min-Heap)

We use a min-heap to track the maximum right endponit of each existing group. The size of the heap at the end directly equals the minimum number of groups needed.

Code Implementation

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

typedef long long LL;
const int MAX_INTERVALS = 100010;

struct Interval {
    LL start, end;
    bool operator<(const Interval& other) const {
        return start < other.start;
    }
} intervals[MAX_INTERVALS];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> intervals[i].start >> intervals[i].end;
    }
    sort(intervals, intervals + n);
    priority_queue<LL, vector<LL>, greater<LL>> min_end_heap;
    for (int i = 0; i < n; ++i) {
        Interval curr = intervals[i];
        if (min_end_heap.empty() || min_end_heap.top() >= curr.start) {
            min_end_heap.push(curr.end);
        } else {
            min_end_heap.pop();
            min_end_heap.push(curr.end);
        }
    }
    cout << min_end_heap.size() << endl;
    return 0;
}

---

Approach 2: Two-Pointer Technique

Separate and sort the start and end points of all intervals. Use two pointers to traverse both sorted arrays: when a start point ≤ current end point, an additional group is needed; otherwise, move the end pointer forward.

Code Implementation (with Comments)

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;
const int MAX_INTERVALS = 100010;

LL starts[MAX_INTERVALS], ends[MAX_INTERVALS];
int n, min_groups;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> starts[i] >> ends[i];
    }
    sort(starts, starts + n);
    sort(ends, ends + n);
    int end_ptr = 0;
    min_groups = 0;
    for (int start_ptr = 0; start_ptr < n; ++start_ptr) {
        if (starts[start_ptr] <= ends[end_ptr]) {
            min_groups++;
        } else {
            end_ptr++;
        }
    }
    cout << min_groups << endl;
    return 0;
}