2534. Time Taken to Cross the Door

There are n persons numbered from 0 to n - 1 and a door. Each person can enter or exit through the door once, taking one second.

You are given a non-decreasing integer array arrival of size n, where arrival[i] is the arrival time of the ith person at the door. You are also given an array state of size n, where state[i] is 0 if person i wants to enter through the door or 1 if they want to exit through the door.

If two or more persons want to use the door at the same time, they follow the following rules:

• If the door was not used in the previous second, then the person who wants to exit goes first.
• If the door was used in the previous second for entering, the person who wants to enter goes first.
• If the door was used in the previous second for exiting, the person who wants to exit goes first.
• If multiple persons want to go in the same direction, the person with the smallest index goes first.

Return an array answer of size n where answer[i] is the second at which the ith person crosses the door.

Note that:

• Only one person can cross the door at each second.
• A person may arrive at the door and wait without entering or exiting to follow the mentioned rules.

class Solution {
public:
    vector<int> timeTaken(vector<int>& arrival, vector<int>& state) {
        vector<int> res(arrival.size(), -1);
        map<int, vector<int>> mp;
        for(int i = 0; i < arrival.size(); i++) mp[arrival[i]].push_back(i);
        priority_queue<int,vector<int>,greater<int>> open, close;
        int st = 1, time = 0;
        mp[INT_MAX] = {};
        for(auto it = begin(mp); it->first != INT_MAX; it++) {
            int nt = next(it)->first;
            time = it->first;
            for(auto idx : it->second) {
                if(state[idx] == 1) close.push(idx);
                else open.push(idx);
            }
            int use = min(nt - time, (int)(open.size() + close.size()));
            while(use) {
                if(open.empty() and close.empty()) break;
                if(st == 1) {
                    if(close.empty()) st = 0;
                    else {
                        res[close.top()] = time++;
                        close.pop();
                        use -= 1;
                    }
                } else if(st == 0) {
                    if(open.empty()) st = 1;
                    else {
                        res[open.top()] = time++;
                        open.pop();
                        use -= 1;
                    }
                }
            }
            if(time != nt) st = 1;
        }
        return res;
    }
};