2534. Time Taken to Cross the Door


Problem Explanation

In this problem, there are n persons who want to enter or exit through a door. Each person can enter or exit through the door once, taking one second. We are given a non-decreasing integer array arrival of size n, where arrival[i] is the arrival time of the ith person at the door. Also, there is an array state of size n, where state[i] is 0 if person i wants to enter through the door or 1 if they want to exit through the door.

The main goal is to find an array answer of size n where answer[i] is the second at which the ith person crosses the door, considering various rules regarding entering and exiting the door.

Example Walkthrough

Consider the example: arrival = [0, 1, 1, 2, 4] state = [0, 1, 0, 0, 1]

The expected output is [0, 3, 1, 2, 4].

Here's how we can process each second:

  • At t = 0: Person 0 is the only one who wants to enter, so they just enter through the door.
  • At t = 1: Person 1 wants to exit, and person 2 wants to enter. Since the door was used the previous second for entering, person 2 enters.
  • At t = 2: Person 1 still wants to exit, and person 3 wants to enter. Since the door was used the previous second for entering, person 3 enters.
  • At t = 3: Person 1 is the only one who wants to exit, so they just exit through the door.
  • At t = 4: Person 4 is the only one who wants to exit, so they just exit through the door.

Therefore, the answer is [0, 3, 1, 2, 4].

Solution Approach

We can use two pointers approach for solving this problem. First, we can create two lists, one for the entering persons and one for the exiting persons, and initialize pointers at the beginning of those lists. Next, we can iterate until both pointers reach the end of their respective lists. Finally, we can follow the rules stated in the problem description for entering and exiting persons and update the answer array accordingly.

Python Solution

1class Solution:
2    def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:
3        n = len(arrival)
4        answer = [0] * n
5        enter = []
6        exit = []
7
8        # Separate entering and exiting persons
9        for i in range(n):
10            if state[i] == 0:
11                enter.append(i)
12            else:
13                exit.append(i)
14
15        enter_ptr = 0
16        exit_ptr = 0
17        prev_action = -1
18        time = 0
19
20        # Iterate until both pointers reach the end
21        while enter_ptr < len(enter) or exit_ptr < len(exit):
22            # Check rules for entering and exiting persons
23            if (enter_ptr < len(enter) and exit_ptr < len(exit) and
24                arrival[enter[enter_ptr]] <= time and arrival[exit[exit_ptr]] <= time):
25                if prev_action == 0:
26                    answer[enter[enter_ptr]] = time
27                    enter_ptr += 1
28                    prev_action = 0
29                else:
30                    answer[exit[exit_ptr]] = time
31                    exit_ptr += 1
32                    prev_action = 1
33            elif enter_ptr < len(enter) and arrival[enter[enter_ptr]] <= time:
34                answer[enter[enter_ptr]] = time
35                enter_ptr += 1
36                prev_action = 0
37            elif exit_ptr < len(exit) and arrival[exit[exit_ptr]] <= time:
38                answer[exit[exit_ptr]] = time
39                exit_ptr += 1
40                prev_action = 1
41            else:
42                prev_action = -1
43
44            time += 1
45
46        return answer

*Note: Solutions for Java, JavaScript, C++, and C# are beyond the scope of this prompt, but following the same approach mentioned above, we can create solutions for those languages as well.*JavaScript Solution

1class Solution {
2    timeTaken(arrival, state) {
3        const n = arrival.length;
4        const answer = Array(n).fill(0);
5        const enter = [];
6        const exit = [];
7
8        // Separate entering and exiting persons
9        for (let i = 0; i < n; i++) {
10            if (state[i] === 0) {
11                enter.push(i);
12            } else {
13                exit.push(i);
14            }
15        }
16
17        let enter_ptr = 0;
18        let exit_ptr = 0;
19        let prev_action = -1;
20        let time = 0;
21
22        // Iterate until both pointers reach the end
23        while (enter_ptr < enter.length || exit_ptr < exit.length) {
24            // Check rules for entering and exiting persons
25            if (enter_ptr < enter.length && exit_ptr < exit.length &&
26                arrival[enter[enter_ptr]] <= time && arrival[exit[exit_ptr]] <= time) {
27                if (prev_action === 0) {
28                    answer[enter[enter_ptr]] = time;
29                    enter_ptr++;
30                    prev_action = 0;
31                } else {
32                    answer[exit[exit_ptr]] = time;
33                    exit_ptr++;
34                    prev_action = 1;
35                }
36            } else if (enter_ptr < enter.length && arrival[enter[enter_ptr]] <= time) {
37                answer[enter[enter_ptr]] = time;
38                enter_ptr++;
39                prev_action = 0;
40            } else if (exit_ptr < exit.length && arrival[exit[exit_ptr]] <= time) {
41                answer[exit[exit_ptr]] = time;
42                exit_ptr++;
43                prev_action = 1;
44            } else {
45                prev_action = -1;
46            }
47
48            time++;
49        }
50
51        return answer;
52    }
53}

Java Solution

1import java.util.*;
2
3class Solution {
4    public int[] timeTaken(int[] arrival, int[] state) {
5        int n = arrival.length;
6        int[] answer = new int[n];
7        List<Integer> enter = new ArrayList<>();
8        List<Integer> exit = new ArrayList<>();
9
10        // Separate entering and exiting persons
11        for (int i = 0; i < n; i++) {
12            if (state[i] == 0) {
13                enter.add(i);
14            } else {
15                exit.add(i);
16            }
17        }
18
19        int enter_ptr = 0;
20        int exit_ptr = 0;
21        int prev_action = -1;
22        int time = 0;
23
24        // Iterate until both pointers reach the end
25        while (enter_ptr < enter.size() || exit_ptr < exit.size()) {
26            // Check rules for entering and exiting persons
27            if (enter_ptr < enter.size() && exit_ptr < exit.size() &&
28                arrival[enter.get(enter_ptr)] <= time && arrival[exit.get(exit_ptr)] <= time) {
29                if (prev_action == 0) {
30                    answer[enter.get(enter_ptr)] = time;
31                    enter_ptr++;
32                    prev_action = 0;
33                } else {
34                    answer[exit.get(exit_ptr)] = time;
35                    exit_ptr++;
36                    prev_action = 1;
37                }
38            } else if (enter_ptr < enter.size() && arrival[enter.get(enter_ptr)] <= time) {
39                answer[enter.get(enter_ptr)] = time;
40                enter_ptr++;
41                prev_action = 0;
42            } else if (exit_ptr < exit.size() && arrival[exit.get(exit_ptr)] <= time) {
43                answer[exit.get(exit_ptr)] = time;
44                exit_ptr++;
45                prev_action = 1;
46            } else {
47                prev_action = -1;
48            }
49
50            time++;
51        }
52
53        return answer;
54    }
55}

These solutions follow the same approach mentioned above and can be used for the respective programming languages.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«