Hotel Room Assignments - Google Top Interview Questions

                        Solution in C++ :

vector<int> solve(vector<vector<int>>& A) {
    set<int> available_rooms;          // set of available rooms
    set<pair<int, int>> booked_rooms;  // {end time, room assigned}

    for (int i = 0; i < A.size(); i++) A[i].push_back(i), available_rooms.insert(i);

    // If requests intervals[i] and intervals[j] have the same starting time, then earlier index
    // min(i, j) is assigned a room first.
    sort(begin(A), end(A), [&](auto& a, auto& b) {
        if (a[0] == b[0])
            return a[2] < b[2];
        else
            return a[0] < b[0];
    });

    vector<int> ans(A.size());  // store rooms assigned to each index

    for (auto& v : A) {
        // make free rooms available
        while (!booked_rooms.empty() && booked_rooms.begin()->first <= v[0]) {
            available_rooms.insert(booked_rooms.begin()->second);
            booked_rooms.erase(booked_rooms.begin());
        }
        // assign rooms
        ans[v[2]] = *available_rooms.begin();
        booked_rooms.insert({v[1], *available_rooms.begin()});
        available_rooms.erase(available_rooms.begin());
    }
    return ans;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    static class Event implements Comparable<Event> {
        int time; // Time of event
        boolean st; // Is starting event or ending event ?
        int idx; // Index in original array

        public Event(int time, boolean st, int idx) {
            this.time = time;
            this.st = st;
            this.idx = idx;
        }

        // Sort events by time, if to events have same time then give more priority to ending event.

        public int compareTo(Event e) {
            if (e.time == this.time) {
                if (!this.st)
                    return -1;
                return 1;
            }
            return this.time - e.time;
        }
    }

    public int[] solve(int[][] intervals) {
        int n = intervals.length;
        Event[] events = new Event[n * 2];

        for (int i = 0, j = 0; i < n; ++i, j += 2) {
            events[j] = new Event(intervals[i][0], true, i);
            events[j + 1] = new Event(intervals[i][1], false, i);
        }

        Arrays.sort(events);

        int[] ans = new int[n];
        int curr = 0;
        int cnt = 0;

        // Line sweep algorithm
        // Count total rooms to be alloted

        for (int i = 0; i < 2 * n; ++i) {
            Event e = events[i];
            if (e.st)
                ++curr;
            else
                --curr;
            cnt = Math.max(cnt, curr);
        }

        // Store available rooms at any instant
        // Initially all rooms are available

        TreeSet<Integer> available = new TreeSet<>();
        for (int i = 0; i < cnt; ++i) available.add(i);

        // For every starting event assign first available room
        // For every ending event free up its alloted room

        for (int i = 0; i < 2 * n; ++i) {
            Event e = events[i];
            if (e.st) {
                int x = available.first();
                available.remove(x);
                ans[e.idx] = x;
            } else
                available.add(ans[e.idx]);
        }
        return ans;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, intervals):
        pq = list(range(len(intervals)))  # Priority queue storing available rooms
        heapify(pq)
        events = []  # This will store the start and end times for each interval
        for index, interval in enumerate(intervals):
            events.append((interval[0], 1, index))
            events.append((interval[1], 0, index))
        res = [0] * len(intervals)  # Stores the output
        for time, event, idx in sorted(events):
            if event:  # We are processing the start of an inteval
                res[idx] = heappop(pq)  # Get smallest available room
            else:
                heappush(pq, res[idx])  # Add the current room back to available rooms
        return res