通过门的时间

2534. 通过门的时间

n 个人，按从 0 到 n - 1 编号。现在有一扇门，每个人只能通过门进入或离开一次，耗时一秒。

给你一个 非递减顺序 排列的整数数组 arrival ，数组长度为 n ，其中 arrival[i] 是第 i 个人到达门前的时间。另给你一个长度为 n 的数组 state ，其中 state[i] 是 0 则表示第 i 个人希望进入这扇门，是 1 则表示 TA 想要离开这扇门。

如果同时有两个或更多人想要使用这扇门，则必须遵循以下规则：

如果前一秒没有使用门，那么想要离开的人会先离开。
如果前一秒使用门进入，那么想要进入的人会先进入。
如果前一秒使用门离开，那么想要离开的人会先离开。
如果多个人都想朝同一方向走（都进入或都离开），编号最小的人会先通过门。

返回一个长度为 n 的数组 answer ，其中 answer[i] 是第 i 个人通过门的时刻（秒）。

注意：

每秒只有一个人可以通过门。
为遵循上述规则，一个人可以在到达门附近后等待，而不通过门进入或离开。

示例 1：

输入：arrival = [0,1,1,2,4], state = [0,1,0,0,1]
输出：[0,3,1,2,4]
解释：每秒发生的情况如下：
- t = 0 ：第 0 个人是唯一一个想要进入的人，所以 TA 可以直接进入。
- t = 1 ：第 1 个人想要离开，第 2 个人想要进入。因为前一秒有人使用门进入，所以第 2 个人先进入。
- t = 2 ：第 1 个人还是想要离开，第 3 个人想要进入。因为前一秒有人使用门进入，所以第 3 个人先进入。
- t = 3 ：第 1 个人是唯一一个想要离开的人，所以 TA 可以直接离开。
- t = 4 ：第 4 个人是唯一一个想要进入的人，所以 TA 可以直接离开。

示例 2：

输入：arrival = [0,0,0], state = [1,0,1]
输出：[0,2,1]
解释：每秒发生的情况如下：
- t = 0 ：第 1 个人想要进入，但是第 0 个人和第 2 个人都想要离开。因为前一秒没有使用门，所以想要离开的人会先离开。又因为第 0 个人的编号更小，所以 TA 先离开。
- t = 1 ：第 1 个人想要进入，第 2 个人想要离开。因为前一秒有人使用门离开，所以第 2 个人先离开。
- t = 2 ：第 1 个人是唯一一个想要进入的人，所以 TA 可以直接进入。

提示：

n == arrival.length == state.length
1 <= n <= 10⁵
0 <= arrival[i] <= n
arrival 按 非递减顺序 排列
state[i] 为 0 或 1

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<int> timeTaken(vector<int>& arrival, vector<int>& state) { } };

cpp 解法, 执行用时: 76 ms, 内存消耗: 74.5 MB, 提交时间: 2023-10-22 10:16:16

class Solution {
public:
    vector<int> timeTaken(vector<int>& arrival, vector<int>& state) {
        int n = state.size(), p[] = {n, n};
        // cout << n << endl;
        for (int i = n -1; i >= 0; --i) {
            int j = state[i];
            state[i] = p[j];
            p[j] = i;
        }
        // for_each(state.begin(), state.end(), [](int v){cout << v << ' ';}); cout << endl;
        arrival.push_back(n<<1);
        for (int preTime = 0, preState = 1; true; ++preTime) {
            if (arrival[p[preState]] > preTime) preState = arrival[p[0]] < arrival[p[1]] ? 0 : 1;
            // cout << preTime << ": (" << p[0] << "," << arrival[p[0]] << ") (" << p[1] << "," << arrival[p[1]] << ") => " << preState << ";\n";
            int i = p[preState];
            if (i == n) break;
            p[preState] = state[i];
            state[i] = preTime = max(preTime, arrival[i]);
        }
        return state;
    }
};

python3 解法, 执行用时: 128 ms, 内存消耗: 34.6 MB, 提交时间: 2023-10-22 10:15:57

class Solution:
    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:
        n=len(arrival)
        ans=[0]*n
        t,door=0,1#时间 门状态
        #进门队员游标 出门队员游标
        cur=[0,0]
        while min(cur) < n:
            #如果 两个游标最小的到达时间都大于 t 
            #把t移动到最小值 门重置到离开优先
            if arrival[min(cur)]>t:
                door=1
                t=arrival[min(cur)]
            while cur[door]<n and arrival[cur[door]]<=t:
                    if state[cur[door]]==door:
                        ans[cur[door]]=t
                        t+=1
                    cur[door]+=1
            door^=1
        return ans

python3 解法, 执行用时: 220 ms, 内存消耗: 35.4 MB, 提交时间: 2023-10-22 10:15:35

class Solution:
    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:

        res = [-1]*len(arrival)

        p = 0 # 表示arrival里当前待进堆的位置
        wait = [[],[]] # 2个优先队列放到一个列表里，就可以直接取用，不需要大量的if-else判断了
        t = 0 # 表示当前时间
        lt = -1 # 上一个通过门的人的通过时间
        l = 1 #上一个通过门的人的类型，如果lt初值小于-1，l的初值设成什么都可以

        while p<len(arrival) or wait[0] or wait[1]:
            while p<len(arrival) and arrival[p]<=t: # 先把已经来到门前等待通过的人都放进优先队列
                heapq.heappush(wait[state[p]],p)
                p+=1
            typ = l if t-lt==1 else 1 # 如果上一秒有人通过，那就和上一秒类型相同的优先，否则出门的优先
            if wait[typ] or wait[typ^1]: # 注意这两个优先队列只要有一个不为空，这一秒就肯定有人要通过门
                l = typ if wait[typ] else typ^1 # 如果优先的一边有人就让优先的一边先过，否则另一边过
                res[heapq.heappop(wait[l])] = t
                lt = t
                t+=1
            else:
                t = arrival[p]  # 这说明没人等待，让时间快进到下一个等待的人能立即通过门，对这道题可以不用这么做而是把t+1放到if外面，但如果这么做，这个代码的时间复杂度将和arrival里的值无关        
        
        return res

上一题

下一题

详情