Problem statement

https://binarysearch.com/problems/Hotel-Room-Assignments/

Solution

Let us keep events of our intervals: if it is started or ended. Also keep heap with avaliable rooms.

  1. If we have starting event, we need to book room, so extract element from heap, this room is not avaliable no more.
  2. If we have ending event, this room is free now, so we can put it back to our heap.

Complexity

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

Code

class Solution:
    def solve(self, I):
        pq, events = list(range(len(I))), []
        for i, (x, y) in enumerate(I):
            events += [(x, 1, i), (y, 0, i)]

        ans = [0] * len(I)
        for time, event, idx in sorted(events):
            if event:
                ans[idx] = heappop(pq)
            else:
                heappush(pq, ans[idx])
        return ans