algoadvance

Leetcode 3168. Minimum Number of Chairs in a Waiting Room

Problem Statement

You are given a list of tuples where each tuple represents the arrival and departure times of a customer in a waiting room of a restaurant. Each tuple (a, d) means the customer arrives at time a and departs at time d. You need to find the minimum number of chairs required so that no customer has to stand while waiting.

Example:
Input: [(1, 4), (2, 3), (3, 6)]
Output: 2

Explanation:
Customer 1: arrives at 1, leaves at 4
Customer 2: arrives at 2, leaves at 3
Customer 3: arrives at 3, leaves at 6

At time 1, one chair is used by Customer 1.
At time 2, two chairs are used (Customer 1 and Customer 2).
At time 3, two chairs are used (Customer 1 and Customer 3 after Customer 2 leaves).
At time 4, one chair is used (Customer 3).

Clarifying Questions

  1. Do customers arrive and leave exactly at the given times?
    • Yes, customers arrive at a and leave at d.
  2. Is the input guaranteed to be sorted?
    • No, the input is not necessarily sorted.
  3. Can there be multiple customers arriving or leaving at the same time?
    • Yes, multiple customers can arrive or leave at the same time.
  4. What is the maximum size of the input list?
    • The size can vary, but we’ll assume it’s reasonably within typical constraints for an interview problem.

Strategy

  1. Events Handling:
    • We will treat this as a problem of tracking overlapping intervals. Each customer generates two events: an arrival (a) and a departure (d).
  2. Sorting Events:
    • We will sort these events by time. If two events have the same time, an arrival event should come before a departure event to avoid counting the same time period twice.
  3. Sweep Line Algorithm:
    • We will use a sweep line algorithm to traverse these events while keeping track of how many chairs are in use at any point in time. The maximum number of chairs used simultaneously will be our answer.

Code

import java.util.Arrays;
import java.util.PriorityQueue;

public class MinimumChairs {
    public static int minChairs(int[][] times) {
        int n = times.length;
        int[][] events = new int[2 * n][2]; // Each customer has two events: (a, 1) and (d, -1)
        
        for (int i = 0; i < n; i++) {
            events[2 * i] = new int[]{times[i][0], 1}; // Arrival increases chairs needed
            events[2 * i + 1] = new int[]{times[i][1], -1}; // Departure decreases chairs needed
        }
        
        Arrays.sort(events, (a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
        
        int maxChairs = 0;
        int currentChairs = 0;
        
        for (int[] event : events) {
            currentChairs += event[1];
            maxChairs = Math.max(maxChairs, currentChairs);
        }
        
        return maxChairs;
    }
    
    public static void main(String[] args) {
        int[][] times = {
            {1, 4},
            {2, 3},
            {3, 6}
        };
        
        System.out.println(minChairs(times));  // Output: 2
    }
}

Time Complexity

  1. Event Generation: O(n), where n is the number of customers.
  2. Sorting Events: O(n log n).
  3. Processing Events: O(n).

Thus, the overall time complexity is O(n log n). This is efficient and suitable for typical input sizes in coding interviews.

This concludes the breakdown of the problem and the solution strategy. Let’s test the solution with the provided example and some additional cases to ensure full coverage.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI