We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Time Taken to Cross the Door

Number: 2617

Difficulty: Hard

Paid? Yes

Companies: Google, IMC, Amazon

Problem Description

There are n persons arriving at a door at given times, each either wishing to enter (state 0) or exit (state 1). At every second the door can process only one person. When multiple persons are waiting at the same second, if the door was idle in the previous second, exiting persons get priority; otherwise, if the door was used for entering in the previous second, then an entering person is processed first, and if the door was used for exiting in the previous second, then an exiting person gets to go first. If several persons in the same direction are waiting, the one with the smallest index crosses first. Given the arrival times and states for all persons, determine at which second each person crosses the door.

Key Insights

  • Since the arrival array is non-decreasing, we can process persons in order while simulating the timeline.
  • Use two queues to separate waiting persons based on their intention: one for entering (state 0) and one for exiting (state 1).
  • Maintain a pointer to traverse the arrival list and add persons to the appropriate waiting queue once their arrival time is reached.
  • Use a simulation loop that increments time second by second (or jumps when no one is waiting) and adheres to the priority rules based on the door’s usage in the previous second.
  • Reset the previous usage state (or treat it as idle) when the door is unused for a second, thereby giving exit priority for the next event if applicable.

Space and Time Complexity

Time Complexity: O(n) – each person is enqueued and dequeued at most once. Space Complexity: O(n) – extra space for storing waiting queues and the result array.

Solution

We simulate the door operation on a timeline by maintaining two queues: one for persons waiting to enter and one for persons waiting to exit. We iterate through each second, and at every second, add all persons whose arrival time is reached to the appropriate waiting queue. Depending on the door's usage in the previous second, we decide which queue gets served:

  • If the door was not used in the immediate previous second, exit requests are prioritized.
  • If the door was last used for entering, then an entering request is prioritized (if available).
  • If the door was last used for exiting, then an exiting request is prioritized. If no one is waiting, we fast-forward time to the next person's arrival. We update the result for each person when they cross, and finally, we return the result array.

Code Solutions

# Python solution for "Time Taken to Cross the Door"

from collections import deque

def timeTaken(arrival, state):
    n = len(arrival)
    # Initialize result array with -1 values
    result = [-1] * n
    
    # Queues to store indices of persons waiting to enter or exit
    waiting_enter = deque()
    waiting_exit = deque()
    
    time = 0         # simulation time
    idx = 0          # pointer to process arrival array
    last_direction = -1  # -1 indicates door unused in previous second
    
    # Process until all persons have crossed
    while idx < n or waiting_enter or waiting_exit:
        # Add all persons arriving at the current time to the appropriate queue
        while idx < n and arrival[idx] <= time:
            if state[idx] == 0:
                waiting_enter.append(idx)
            else:
                waiting_exit.append(idx)
            idx += 1
        
        # If no one is waiting, fast-forward time to the next arrival time and reset last_direction
        if not waiting_enter and not waiting_exit:
            time = arrival[idx]
            last_direction = -1
        
        # Decision making based on previous door usage
        else:
            # Decide based on the last used direction
            if last_direction == -1:
                # Door idle last second: exit gets priority if available
                if waiting_exit:
                    cur = waiting_exit.popleft()
                    last_direction = 1
                else:
                    cur = waiting_enter.popleft()
                    last_direction = 0
            elif last_direction == 1:
                # Last action was exit: exit gets priority if available
                if waiting_exit:
                    cur = waiting_exit.popleft()
                    last_direction = 1
                else:
                    cur = waiting_enter.popleft()
                    last_direction = 0
            else:  # last_direction == 0, last action was enter
                # In this case, entering gets priority if available
                if waiting_enter:
                    cur = waiting_enter.popleft()
                    last_direction = 0
                else:
                    cur = waiting_exit.popleft()
                    last_direction = 1
            # Record the result
            result[cur] = time
            # Move simulation time forward by one second
            time += 1
    return result

# Example usage:
#print(timeTaken([0,1,1,2,4], [0,1,0,0,1]))  # Expected output: [0,3,1,2,4]
#print(timeTaken([0,0,0], [1,0,1]))            # Expected output: [0,2,1]
← Back to All Questions