2534：通过门的时间（★★）

力扣第 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 <= 105
• 0 <= arrival[i] <= n
• arrival 按 非递减顺序 排列
• state[i] 为 0 或 1

分析

• 两个堆 L/R 维护等待进入/离开的人集合
• pre 维护前一秒使用门的状态，模拟即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution:
    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:
        n = len(arrival)
        res = [-1]*n
        L,R = [],[]
        t,i = 0,0
        pre = -1
        while True:
            while i<n and arrival[i]<=t:
                heappush(R if state[i] else L,i)
                i += 1
            if (not L or pre!=0) and R:
                j = heappop(R)
                res[j] = t
                t += 1
                pre = 1
            elif L:
                j = heappop(L)
                res[j] = t
                t += 1
                pre = 0
            elif i<n:
                t = arrival[i]
                pre = -1
            else:
                break
        return res

88 ms