Problem statement

https://binarysearch.com/problems/Revolving-Door/

Solution

You need to code quite a lot in this problem to mark it as easy. Basically what we need to do is carefully simulate process, but we need to deal with some edge cases. Denote by events correspondences time -> [number of in, number of out]. Then we traverse times in sorted order and:

  1. If t > time, it means we do not have queue, update time and direction.
  2. x and y are number of persons want to go in and out. Notice, that we start with persons with direction first.
  3. First let all person with direction go in/out and then for all others.
  4. Update time. If we have some persons with direction ^ 1, change direction.

Complexity

It is O(n log n) for time and O(n) for space.

Code

#### CODE by Awice
class Solution:
    def solve(self, requests):
        events = defaultdict(lambda: [0, 0])
        for t, d in requests:
            events[t][d] += 1

        ans = []
        direction = 1
        time = 0
        for t in sorted(events):
            if t > time:
                time = t
                direction = 1

            x = events[t][direction]
            y = events[t][direction ^ 1]

            for t in range(time, time + x):
                ans.append([t, direction])
            for t in range(time + x, time + x + y):
                ans.append([t, direction ^ 1])

            time += x + y
            if y:
                direction ^= 1

        return ans