时间复杂度O(NlogN + N)

#include <iostream>
#include <algorithm>
#include <vector>

//差分
using namespace std;
#define time first
#define id second
const int N = 1e5 + 10;
typedef pair<int , int > PII;
vector<PII> a;
int shop[N];  //差分
int n;
int m;
int T;
bool compare(PII a , PII b){
    if (a.id != b.id) return a.id < b.id;
    return a.time < b.time;
}
int main (){
    cin >> n >> m >> T;
    for (int i = 0;i < m;i++){
        int t = 0;
        int ID = 0;
        cin >> t >> ID;
        a.push_back({t , ID});
    }
    //按照id为第一个关键词，time为第二关键词 从小到大排序
    sort(a.begin() , a.end() ,compare);  
    //for (int i = 0;i < m;i++) cout << a[i].id << " " << a[i].time << endl;
    //为每个店铺处理订单
    //对于一个新的订单，比较和前一个订单的时间差
    //如果时间差是1或者0则说明不用-1
    //如果时间差大于1那么订单需要减去时间差-1的优先级
    //如果下一个订单开始是另一个店铺的，则为当前这个店铺结算优先级
    //如果最后一个订单不是T时刻，那么需要减去对于的时间差
    int res = 0;
    int cur = 2; //当前的优先级  因为第一个订单是一定存在的
    bool st = false; //表示是否在缓存中
    for (int i = 1;i < a.size();i++){
        if (a[i].id != a[i - 1].id){
            //新的店铺开始了
            //结算上个店铺的优先级
            cur -= (T - a[i - 1].time);
            if (cur <= 3) st = false;
            if (st) res++ ;//cout << a[i - 1].id << endl;
            cur = 2;
            st = false;
            continue;
        }//if
        int sub = a[i].time - a[i - 1].time;  //上一个订单到这个订单的中间时间间隔
        if (sub > 1){
            cur -= (sub - 1);
            if (cur < 0) cur = 0; //优先级最小为0
        }//if
            if (cur <= 3) st = false;  //从缓存中移出来
            cur += 2;  //加上当前这个订单的优先级
            if (cur > 5) st = true;  //加入缓存
    }
    //处理最后一个订单
    cur = cur - (T - a[m - 1].time);
    if (cur <= 3) st = false;
    if (st) res++;
    cout << res << endl;
    return 0;
}