Queues
Applications
Simulation Problem
- Use states
- Separate queues if possible (enter pool, leave pool)
- Separate states whenever possible (avoid overlapping states that might be used to store the state of multiple items)
- Iterate the time instead of (separating arrival by state then iterating the queues, keeping track of who has arrived will be difficult)
- Multiple arrivals are easily managed this way
def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:
enter_pool, exit_pool = deque(),deque()
cur_time = 0
prev_state = 1
i = 0
ans = [0 for _ in range(len(arrival))]
while i < len(arrival) or enter_pool or exit_pool:
while i < len(arrival) and arrival[i] <= cur_time:
if state[i] == 0:
enter_pool.append(i)
else:
exit_pool.append(i)
i += 1
if prev_state == 1:
if exit_pool:
ans[exit_pool.popleft()] = cur_time
elif enter_pool:
ans[enter_pool.popleft()] = cur_time
prev_state = 0
else:
if enter_pool:
ans[enter_pool.popleft()] = cur_time
elif exit_pool:
ans[exit_pool.popleft()] = cur_time
prev_state = 1
else:
prev_state = 1
cur_time += 1
return ans