algoadvance

Leetcode 3168. Minimum Number of Chairs in a Waiting Room

Problem Statement

You’re given a list of tuples representing the arrival and departure times of people visiting a waiting room. Your task is to determine the minimum number of chairs required such that no person has to wait standing.

Each tuple (a, b) represents a visitor who arrives at time a and leaves at time b.

Example

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

Clarifying Questions

  1. Are the times given in a 24-hour format?
    • Yes, it can be assumed that the times are in integer format.
  2. Can two events have the same start and end times?
    • Yes, multiple events can start or end at the same time.
  3. What is the maximum possible length of input?
    • Assume the length of input can be up to 10^4.

Strategy

  1. Separate and Sort Events:
    • Create two lists: one for arrivals and one for departures.
    • Sort both lists.
  2. Simulate Room Usage:
    • Use two pointers to traverse the sorted arrivals and departures.
    • Increment the number of chairs on each arrival, decrement on each departure.
    • Track the maximum number of simultaneous chairs needed during the simulation.

Code

Here’s how you might implement this in C++:

#include <iostream>
#include <vector>
#include <algorithm>

int minChairsRequired(std::vector<std::pair<int, int>> intervals) {
    std::vector<int> arrivals, departures;
    for (auto interval : intervals) {
        arrivals.push_back(interval.first);
        departures.push_back(interval.second);
    }
    
    std::sort(arrivals.begin(), arrivals.end());
    std::sort(departures.begin(), departures.end());
    
    int arrivalIdx = 0, departureIdx = 0;
    int currentChairs = 0, maxChairs = 0;
    
    while (arrivalIdx < arrivals.size()) {
        if (arrivals[arrivalIdx] < departures[departureIdx]) {
            currentChairs++;
            arrivalIdx++;
            if (currentChairs > maxChairs) {
                maxChairs = currentChairs;
            }
        } else {
            currentChairs--;
            departureIdx++;
        }
    }
    
    return maxChairs;
}

int main() {
    std::vector<std::pair<int, int>> intervals = \{\{1, 4}, {2, 3}, {3, 6}, {5, 7}};
    std::cout << "Minimum Number of Chairs Required: " << minChairsRequired(intervals) << std::endl;
    return 0;
}

Time Complexity

Given that sorting dominates, the overall time complexity is O(n log n), which is efficient enough for n up to 10^4.

Conclusion

The algorithm separates arrival and departure times, sorts them, and then simulates room usage to find the maximum number of chairs required at any point in time. This solution efficiently handles the problem within the given constraints.

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