UPC9568 zzs妹子

题目描述

zzs和他的n个妹子快乐的生活在一起。
有一天，zzs的妹子们想喝水。第i个妹子想在li到ri（包括端点）的时间内喝水。
每个妹子喝水的时候都需要用水杯，每个水杯只能同时被一个妹子用。由于妹子都非常可爱，zzs当然不忍心让她们渴着。请问zzs至少买多少个水杯才能满足妹子们的要求？

输入

第一行一个整数n。
第2行到第n+1行，每行两个整数，第i+1行的两个整数表示li,ri。（1≤n≤2×105,1≤li≤ri≤109）

输出

一行一个整数表示答案。

样例输入

复制样例数据

3
1 2
2 3
3 4

样例输出

2


与教室安排节目不同，这里需要求最少的杯子数，应当优先安排开始时间早的人。

#include "bits/stdc++.h"
 
using namespace std;
const int maxn = 2e5 + 100;
const int mod = 1e9 + 7;
typedef long long ll;
struct node {
    int l, r;
 
} e[maxn];
//int beizi[maxn];
priority_queue<int, vector<int>, greater<int> > q;
 
bool cmp(node a, node b) {
    if (a.l != b.l) {
        return a.l < b.l;
    } else {
        return a.r < b.r;
    }
}
 
int main() {
    //freopen("input.txt", "r", stdin);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> e[i].l >> e[i].r;
    }
    sort(e, e + n, cmp);
    q.push(0);
    for (int i = 0; i < n; i++) {
        if (q.top() < e[i].l) {
            q.pop();
            q.push(e[i].r);
        } else {
            q.push(e[i].r);
        }
    }
    cout << q.size() << endl;
    return 0;
}