algoadvance

You are given an array of time intervals where some people arrive and leave a waiting room. Each interval is represented by a pair of integers [start, end], where start indicates the time of arrival and end the time of departure.

You need to determine the minimum number of chairs required in the waiting room so that no one has to wait standing.

Example: Input: intervals = [[1, 4], [2, 3], [3, 6], [5, 7]] Output: 3

Clarifying Questions

  1. Are the intervals inclusive of both start and end times?
    • For the sake of the problem, we assume intervals are inclusive.
  2. Are the intervals guaranteed to be positive integers?
    • Yes, the intervals will have positive integer values.
  3. Can intervals have overlapping times?
    • Yes, intervals can overlap, which is why calculating the number of chairs is necessary.
  4. Is the input given in any specific order?
    • Not necessarily. The input can be unsorted.

Strategy

  1. Separate Events: Create two lists, one for arrival times and one for departure times.
  2. Sort Events: Sort both lists.
  3. Two-Pointer Technique: Use a two-pointer technique to iterate over the arrival and departure times:
    • Increment the chair count when a person arrives.
    • Decrement the chair count when a person leaves.
  4. Track Maximum Chairs: Maintain a running count of chairs in use and update the maximum requirement as needed.

Time Complexity

Thus, the overall time complexity is O(n log n).

Code

def min_chairs_required(intervals):
    if not intervals:
        return 0

    arrivals = sorted([interval[0] for interval in intervals])
    departures = sorted([interval[1] for interval in intervals])

    min_chairs = 0
    current_chairs = 0
    i, j = 0, 0

    while i < len(arrivals) and j < len(departures):
        if arrivals[i] <= departures[j]:
            current_chairs += 1
            min_chairs = max(min_chairs, current_chairs)
            i += 1
        else:
            current_chairs -= 1
            j += 1

    return min_chairs

# Example usage:
intervals = [[1, 4], [2, 3], [3, 6], [5, 7]]
print(min_chairs_required(intervals))  # Output: 3

This function computes the minimum number of chairs required in the waiting room based on the given time intervals.

Try our interview co-pilot at AlgoAdvance.com