Problem Description

The Restaurant Growth problem asks you to determine the maximum number of customers that are present in a restaurant at the same time, given a list of customer arrival and departure times.

You are given a list of intervals, where each interval [arrive, leave] represents a customer who arrives at time arrive and leaves at time leave. A customer is considered present in the restaurant from arrive (inclusive) up to but not including leave.

Constraints:

• Each customer is represented by exactly one interval.
• No two intervals for the same customer.
• Multiple customers may have overlapping intervals.
• Your goal is to return the maximum number of customers present at any point in time.

Thought Process

To solve this problem, let's first consider the brute-force way: for every possible time unit, count how many customers are present. But this is inefficient if the time range is large.

We realize that the only times the number of customers change is when someone arrives or leaves. So, instead of checking every possible moment, we can just process these "events" (arrivals and departures).

The key insight is to treat each arrival as +1 and each departure as -1 to the current count of customers. By sorting all these events by time and processing them in order, we can keep a running count of customers in the restaurant and track the maximum at any point.

This turns the problem from a potentially slow simulation to a much faster scan of sorted events.

Solution Approach

Here’s how we can efficiently solve the problem:

1. Event Representation:
   • For each customer, create two events: one for arrival (arrive, +1) and one for departure (leave, -1).
2. Sorting:
   • Sort all events by time. If two events have the same time, process departures before arrivals. This ensures that if a customer leaves at the same time another arrives, the count does not temporarily spike.
3. Sweep Line:
   • Initialize a variable to keep track of the current number of customers and another to track the maximum seen so far.
   • Iterate through the sorted events, updating the current count and the maximum as you go.

This approach is known as the sweep line algorithm and is commonly used for interval overlap problems.

Example Walkthrough

Suppose we have the following intervals:

• Customer 1: [1, 4]
• Customer 2: [2, 5]
• Customer 3: [7, 9]

Step 1: Create Events
Events: (1, +1), (4, -1), (2, +1), (5, -1), (7, +1), (9, -1)

Step 2: Sort Events
Sorted: (1, +1), (2, +1), (4, -1), (5, -1), (7, +1), (9, -1)

Step 3: Sweep Through Events

• At time 1: +1 → current = 1, max = 1
• At time 2: +1 → current = 2, max = 2
• At time 4: -1 → current = 1, max = 2
• At time 5: -1 → current = 0, max = 2
• At time 7: +1 → current = 1, max = 2
• At time 9: -1 → current = 0, max = 2

Time and Space Complexity

Brute-force Approach:

• If you checked every possible time between the earliest arrival and latest departure, and for each time checked all intervals, the complexity would be O(T*N), where T is the time range and N is the number of customers.

• We create 2N events (arrival and departure for each customer).
• Sorting the events takes O(N log N).
• Sweeping through the events is O(N).
• So, the total time complexity is O(N log N) and space complexity is O(N) for storing events.

This is much more efficient, especially for large N or wide time ranges.

Summary

The Restaurant Growth problem is a classic interval overlap problem. The key insight is to process only the times when customers arrive or leave, using a sweep line algorithm. By representing arrivals as +1 and departures as -1, sorting the events, and sweeping through them, we efficiently compute the maximum number of customers present at any time. This approach is elegant, efficient, and scales well with the number of customers.

Code Implementation

def restaurantGrowth(intervals):
    events = []
    for arrive, leave in intervals:
        events.append((arrive, 1))   # arrival event
        events.append((leave, -1))   # departure event

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

    current = 0
    max_customers = 0
    for time, change in events:
        current += change
        max_customers = max(max_customers, current)
    return max_customers
      

#include <vector>
#include <algorithm>
using namespace std;

int restaurantGrowth(vector<vector<int>>& intervals) {
    vector<pair<int, int>> events;
    for (auto& interval : intervals) {
        events.push_back({interval[0], 1});   // arrival
        events.push_back({interval[1], -1});  // departure
    }
    sort(events.begin(), events.end(), [](const pair<int,int>& a, const pair<int,int>& b) {
        if (a.first == b.first) return a.second < b.second;
        return a.first < b.first;
    });
    int current = 0, max_customers = 0;
    for (auto& e : events) {
        current += e.second;
        if (current > max_customers) max_customers = current;
    }
    return max_customers;
}
      

import java.util.*;

public class Solution {
    public int restaurantGrowth(int[][] intervals) {
        List<int[]> events = new ArrayList<>();
        for (int[] interval : intervals) {
            events.add(new int[]{interval[0], 1});  // arrival
            events.add(new int[]{interval[1], -1}); // departure
        }
        events.sort((a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
        int current = 0, maxCustomers = 0;
        for (int[] event : events) {
            current += event[1];
            maxCustomers = Math.max(maxCustomers, current);
        }
        return maxCustomers;
    }
}
      

function restaurantGrowth(intervals) {
    const events = [];
    for (const [arrive, leave] of intervals) {
        events.push([arrive, 1]);
        events.push([leave, -1]);
    }
    events.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);
    let current = 0;
    let maxCustomers = 0;
    for (const [time, change] of events) {
        current += change;
        if (current > maxCustomers) maxCustomers = current;
    }
    return maxCustomers;
}