Table Reservation-Coding Problem

Problem Description

Given a 2D array reservations, where each sub-array consists of two integers representing the start and end times of a reservation, the task is to determine the minimum number of tables required to accommodate all reservations without overlapping.

With the input [[0, 5], [2, 5], [5, 10]], the output should be 2, as at least two tables are needed to handle overlapping reservations.

Brute Force

For the first approach we will check every pair of reservations to see if they overlap. If two reservations overlap, they cannot share the same table. We keep a counter of the maximum number of overlaps found, which will correspond to the number of tables required.

    public static int findNumberOfTablesBrute(int[][] reservations) {
        if (reservations == null || reservations.length == 0) {
            return 0;
        }

        int maxTables = 0;

        for (int i = 0; i < reservations.length; i++) {
            int count = 1; // Count
            for (int j = 0; j < reservations.length; j++) {
                if (i != j && reservations[i][0] < reservations[j][1] && reservations[j][0] < reservations[i][1]) {
                    count++;
                }
            }
            maxTables = Math.max(maxTables, count);
        }

        return maxTables;
    }

Time Complexity: O(n²) since we compare each reservation with every other reservation.

i != j:

• This ensures that we are not comparing a reservation with itself. The brute force approach involves checking every pair of different reservations, so this condition avoids comparing a reservation’s time range against itself.

reservations[i][0] < reservations[j][1]:

• This condition checks if the start time of the reservation at index i is earlier than the end time of the reservation at index j. This means that the reservation i starts before the reservation j ends, which is a necessary condition for overlap.

reservations[j][0] < reservations[i][1]:

• This condition checks if the start time of the reservation at index j is earlier than the end time of the reservation at index i. This means that the reservation j starts before the reservation i ends, which is another necessary condition for overlap.

When both of these conditions are true (along with i != j), it means that the time intervals for reservations i and j overlap, indicating that they cannot share the same table. Therefore, these reservations contribute to the count of tables needed.

Lets look at more optimized version.

PriorityQueue

Steps:

Get sunimal malkakulage’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Sort Reservations by Start Time.

Use Min-Heap to Track End Times:

• For each reservation, remove from the heap all reservations that have ended
• Add the current reservation’s end time to the heap.

Determine Maximum Heap Size:

• The size of the heap during processing gives the number of tables need

    public static int findNumberOfTables(int[][] reservations) {
        if (reservations == null || reservations.length == 0) {
            return 0;
        }

        // Sort reservations by start time
        Arrays.sort(reservations, ( a, b) -> a[0] - b[0]);

        // Min-heap　PriorityQueue to keep track of the end times 
        PriorityQueue<Integer> heap = new PriorityQueue <> ();

        // Add the end time of the first reservation
        heap.add(reservations[0][1]);

        for (int i = 1; i < reservations.length; i++) {
            // If the current reservation starts 
            //after or when the earliest reservation ends,
            // remove the earliest reservation
            if (reservations[i][0] >= heap.peek()) {
                heap.poll();
            }
            // Add the end time of the current reservation
            heap.add(reservations[i][1]);

        }

        // The size of the heap =  number of tables needed
        return heap.size();
    }

Time Complexity: O(nlogn), dominated by the sorting and heap operations.

Iterative Solution

The iterative solution involves sorting the start and end times of the reservations as events. We then process these events to find the maximum number of active reservations at any point in time, which determines the number of tables needed.

Steps:

• Create events for each start and end time.
• Sort these events, prioritizing end times over start times if they occur at the same moment.
• Traverse the sorted events, keeping track of the number of current active reservations and updating the maximum count.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class IterativeSolution {
    public static int findMinimumTables(int[][] reservations) {
        List<int[]> events = new ArrayList<>();
        
        for (int[] reservation : reservations) {
            events.add(new int[] {reservation[0], 1});  // Start time event
            events.add(new int[] {reservation[1], -1}); // End time event
        }
        
        Collections.sort(events, (a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
        
        int maxTables = 0;
        int currentTables = 0;
        
        for (int[] event : events) {
            currentTables += event[1];
            maxTables = Math.max(maxTables, currentTables);
        }
        
        return maxTables;
    }

    public static void main(String[] args) {
        int[][] reservations = { {0, 5}, {2, 5}, {5, 10} };
        System.out.println(findMinimumTables(reservations)); // Output: 2
    }
}

Overall Time Complexity

• The most time-consuming step in this algorithm is the sorting step, which has a time complexity of O(n log n).
• Therefore, the overall time complexity of the findMinimumTables method is O(n log n).

this ensures that this algorithm also able handle a large number of reservations reasonably well.