Problem

There is a party where n friends numbered from 0 to n - 1 are attending. There is an infinite number of chairs in this party that are numbered from 0 to infinity. When a friend arrives at the party, they sit on the unoccupied chair with the smallest number.

  • For example, if chairs 0, 1, and 5 are occupied when a friend comes, they will sit on chair number 2.

When a friend leaves the party, their chair becomes unoccupied at the moment they leave. If another friend arrives at that same moment, they can sit in that chair.

You are given a 0-indexed 2D integer array times where times[i] = [arrivali, leavingi], indicating the arrival and leaving times of the ith friend respectively, and an integer targetFriend. All arrival times are distinct.

Return the chair number that the friend numbered targetFriend will sit on.

Examples

Example 1:

Input: times = [[1,4],[2,3],[4,6]], targetFriend = 1
Output: 1
Explanation: 
- Friend 0 arrives at time 1 and sits on chair 0.
- Friend 1 arrives at time 2 and sits on chair 1.
- Friend 1 leaves at time 3 and chair 1 becomes empty.
- Friend 0 leaves at time 4 and chair 0 becomes empty.
- Friend 2 arrives at time 4 and sits on chair 0.
Since friend 1 sat on chair 1, we return 1.

Example 2:

Input: times = [[3,10],[1,5],[2,6]], targetFriend = 0
Output: 2
Explanation: 
- Friend 1 arrives at time 1 and sits on chair 0.
- Friend 2 arrives at time 2 and sits on chair 1.
- Friend 0 arrives at time 3 and sits on chair 2.
- Friend 1 leaves at time 5 and chair 0 becomes empty.
- Friend 2 leaves at time 6 and chair 1 becomes empty.
- Friend 0 leaves at time 10 and chair 2 becomes empty.
Since friend 0 sat on chair 2, we return 2.

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Using Map and Priority Queue

Here is the idea:

  1. Simulate the Chair Allocation: When a friend arrives, we need to find the smallest unoccupied chair. When they leave, that chair becomes available again.
  2. Two Events:
    • Arrival events where a friend occupies the smallest available chair.
    • Leaving events where a chair is freed up.
  3. Sorting: First, sort all events (both arrival and departure) by time. For events happening at the same time, handle departures before arrivals to ensure that any chair vacated is available immediately.
  4. Data Structures:
    • Use a priority queue to keep track of the smallest available chairs.
    • Use a map (or hashmap) to associate each friend with their allocated chair.

Here is the approach:

  1. Parse and sort the events.
  2. Use a priority queue to manage chair allocation.
  3. When processing arrivals, allocate the smallest available chair.
  4. When processing departures, mark the chair as available again.
  5. Return the chair number of the target friend.

Code

Java
public class Solution {
    public int smallestChair(int[][] times, int targetFriend) {
        // List to hold all events
        List<int[]> events = new ArrayList<>();
        
        // Create events for arrivals and departures
        for (int i = 0; i < times.length; i++) {
            events.add(new int[]{times[i][0], 1, i});  // Arrival event
            events.add(new int[]{times[i][1], 0, i});  // Departure event
        }

        // Sort events: first by time, then by type (departure before arrival if same time)
        events.sort((a, b) -> {
            if (a[0] == b[0]) {
                return Integer.compare(a[1], b[1]);
            } else {
                return Integer.compare(a[0], b[0]);
            }
        });

        // Priority queue to track smallest available chairs
        PriorityQueue<Integer> availableChairs = new PriorityQueue<>();
        for (int i = 0; i < times.length; i++) {
            availableChairs.add(i);
        }

        // Map to store which chair a friend is sitting on
        Map<Integer, Integer> friendChairMap = new HashMap<>();

        // Process each event
        for (int[] event : events) {
            int time = event[0];
            boolean isArrival = event[1] == 1;
            int friendIdx = event[2];

            if (isArrival) {
                int chair = availableChairs.poll();  // Get the smallest available chair
                friendChairMap.put(friendIdx, chair);  // Assign the chair to the friend
                if (friendIdx == targetFriend) {
                    return chair;  // If it's the target friend, return the chair number
                }
            } else {
                availableChairs.add(friendChairMap.get(friendIdx));  // Free the chair
            }
        }

        return -1;  // Should not reach here if inputs are valid
    }
}
Python
class Solution:
    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
        # List to hold all events
        events = []
        
        # Create events for arrivals and departures
        for i, (arrive, leave) in enumerate(times):
            events.append((arrive, True, i))  # Arrival event
            events.append((leave, False, i))  # Departure event

        # Sort events: first by time, then by type (departure before arrival if same time)
        events.sort(key=lambda x: (x[0], not x[1]))

        # Priority queue to track smallest available chairs
        available_chairs = list(range(len(times)))
        heapq.heapify(available_chairs)
        
        # Dictionary to store which chair a friend is sitting on
        friendChairMap = {}

        # Process each event
        for time, is_arrival, friend_idx in events:
            if is_arrival:
                chair = heapq.heappop(available_chairs)  # Get the smallest available chair
                friendChairMap[friend_idx] = chair  # Assign the chair to the friend
                if friend_idx == targetFriend:
                    return chair  # If it's the target friend, return the chair number
            else:
                heapq.heappush(available_chairs, friendChairMap[friend_idx])  # Free the chair

        # Should not reach here if inputs are valid
        return -1

Complexity

  • ⏰ Time complexity: O(n log n), due to sorting events and operations on the priority queue.
  • 🧺 Space complexity: O(n) for maintaining the priority queue and mapping.

Method 2 - Using Two Priority Queues

Here are the steps:

  • We need to sort the times based on arrival time, which means we will loose the order of friends. So, before that, store the arrivalTime of targetFriend, since all the the arrival times are distinct this can be used to identify the targetFriend in sorted array.
  • Store all the available seats(one for each friend) in minHeap as available. Because we need to choose the min available chair number
  • Sort the times array based on arrival time.
  • Maintain another minHeap to store leavingTime and occupiedSeat.
  • loop through sorted array
    • remove all the friends from the heap whose leavingTime is less than or equal to current arraival time and add the occupied seats back to available heap.
    • if the current start is equal to targetStart return the min available seat.
    • else add the current leaving time and min available seat to heap.

Code

Java
class Solution {
    
    public int smallestChair(int[][] times, int targetFriend) {
        // Time at which targetFriend arrives
        int targetStart = times[targetFriend][0];

        // Sort the times array based on arrival times
        Arrays.sort(times, (a, b) -> a[0] - b[0]);

        // Priority queue (min-heap) to store available chairs
        PriorityQueue<Integer> available = new PriorityQueue<>();
        for (int i = 0; i < times.length; ++i) {
            available.offer(i);
        }

        // Priority queue (min-heap) to store departure times and associated chairs
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);

        // Process each friend based on sorted arrival times
        for (int i = 0; i < times.length; ++i) {
            // Free up chairs based on departure times before the current arrival time
            while (!pq.isEmpty() && pq.peek()[0] <= times[i][0]) {
                available.offer(pq.poll()[1]);
            }

            // If we reach the target friend, break and return the smallest available chair
            if (times[i][0] == targetStart) {
                break;
            }

            // Assign the smallest available chair to the current friend and add their departure time to the priority queue
            pq.offer(new int[]{times[i][1], available.poll()});
        }

        // Return the smallest available chair for the target friend
        return available.peek();
    }
}
Python
class Solution:
    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
        # Time at which targetFriend arrives
        targetStart = times[targetFriend][0]

        # Sort the times array based on arrival times
        times.sort(key=lambda x: x[0])

        # Priority queue (min-heap) to store available chairs
        available = list(range(len(times)))
        heapq.heapify(available)

        # Priority queue (min-heap) to store departure times and associated chairs
        pq = []

        # Process each friend based on sorted arrival times
        for i in range(len(times)):
            # Free up chairs based on departure times before the current arrival time
            while pq and pq[0][0] <= times[i][0]:
                heapq.heappush(available, heapq.heappop(pq)[1])
            
            # If we reach the target friend, break and return the smallest available chair
            if times[i][0] == targetStart:
                break

            # Assign the smallest available chair to the current friend and add their departure time to the priority queue
            heapq.heappush(pq, (times[i][1], heapq.heappop(available)))

        # Return the smallest available chair for the target friend
        return available[0]

Complexity

  • ⏰ Time complexity: O(NNNXXXNNN)
  • 🧺 Space complexity: O(NNNXXX)