leetcode2402

class Solution {
    using ll = long long;
    vector<ll> mend;
    ll find_room_before(ll time) {
        ll ret = -1;
        auto me = min_element(mend.begin(), mend.end());
        if (*me > time) {
            return me - mend.begin();
        }
        for (int i = 0; i < mend.size(); ++i) {
            if (mend[i] <= time && ret == -1) {
                ret = i;
                break;
            }
        }
        return ret;
    }
public:
    int mostBooked(int n, vector<vector<int>>& mt) {
        sort(mt.begin(), mt.end());
        vector<ll> mcnt(n);
        mend = vector<ll>(n, -1);

        for (auto meeting: mt) {
            ll rid = find_room_before(meeting[0]);
            mcnt[rid]++;
            ll end = max(mend[rid], (ll)meeting[0]) + meeting[1] - meeting[0];
            mend[rid] = end;
        }
        ll ret = 0, max_mt = mcnt[0];
        for (int i = 1; i < mcnt.size(); ++i) {
            if (mcnt[i] > max_mt) {
                max_mt = mcnt[i];
                ret = i;
            }
        }
        return ret;
    }
};