题目
题意简介
给出每个人到旋转门的时间和进出方向，按先后顺序进出，优先前一个时刻同方向的进出。
算法
- 建立两个队列，分别记录当前可以enter和leave的人；
- 按照时刻分组，当一个时刻的人全部读取完后；
- 贪心地把与前一个时刻同方向的全部处理
- 如果到下一个有人到达的时刻之间还有时间，则处理部分另一个方向的人
- 如果下一个时刻与当前最后时刻之间有间隙，需要重置preState为1（leave）
代码
# time = [0, 0, 1, 5]
# direction = [0, 1, 1, 0]
# time = [0, 0, 5, 5]
# direction = [0, 1, 1, 0]
time = [0, 1, 1, 3, 3]
direction = [0, 1, 0, 0, 1]
# time = [1, 2, 4]
# direction = [0, 1, 1]
# time = [1, 1, 3, 3, 4, 5, 6, 7, 7]
# direction = [1, 1, 0, 0, 0, 1, 1, 1, 1]
enter = deque()
leave = deque()
ans = [-1] * len(time)
preState = 1 # leave
lastUsed = -1 # last used time
cur = 0 # current time
for i, t in enumerate(time):
if t > lastUsed + 1:
preState = 1
cur = t
if direction[i] == 0:
enter.append(i)
else:
leave.append(i)
if i == len(time) - 1 or t != time[i+1]:
if preState == 1:
while leave:
ans[leave.popleft()] = cur
cur += 1
while enter and (i == len(time) - 1 or cur < time[i+1]):
ans[enter.popleft()] = cur
cur += 1
preState = 0
elif preState == 0:
while enter:
ans[enter.popleft()] = cur
cur += 1
while leave and (i == len(time) - 1 or cur < time[i+1]):
ans[leave.popleft()] = cur
cur += 1
preState = 1
lastUsed = cur - 1
print(ans)
评论 (0)
