L7. N Meetings in One Room | Greedy Algorithms

1. Problem Statement & Context

The "N Meetings in One Room" problem is a classic scheduling optimization challenge frequently asked in coding interviews.

• The Setup: You are given a single meeting room and a set of $N$ meetings. Each meeting has a designated start time and end time.
• The Constraint: Because there is only one meeting room, meetings cannot overlap. If a meeting is currently taking place, the room is occupied, and no other meeting can start until it finishes.
• The Objective: Maximize the total number of meetings that can be successfully scheduled in the single meeting room. Optionally, the interviewer may also ask you to return the exact order or sequence in which the meetings should be conducted.

2. Core Mental Model: The Greedy Intuition

To maximize the number of meetings, we must avoid squandering room availability.

Real-Life Analogy

Imagine you are booking a conference hall for an entire day. If you choose a meeting that runs for 8 hours straight (e.g., from 9:00 AM to 5:00 PM), you block out the room for the whole day, sacrificing 4 or 5 shorter meetings that could have fit into that same window. To maximize productivity, you naturally want meetings that end as quickly as possible so the room becomes free for the next task.

• The Greedy Strategy: Always prioritize the meeting that ends the earliest. By finishing current meetings faster, we leave maximum remaining time on the clock to accommodate subsequent meetings.

3. Naive Approach vs. Optimal Greedy Approach

Let's examine a concrete set of meetings to understand why naive ordering fails and why sorting by end time succeeds.

Sample Meeting Dataset

Why Naive Sequencing Fails

If we simply process meetings in their original input order (1 to 6):

1. Meeting 1 (0-5): Scheduled (Room occupied until time 5).
2. Meeting 2 (3-4): Skipped (Room is busy).
3. Meeting 3 (1-2): Skipped (Room is busy).
4. Meeting 4 (5-9): Skipped (Room is busy until time 5, but wait—starts at 5? Let's check: room becomes free at 5, so technically 5 is allowed, but let's look further).
5. Meeting 5 (5-7): Skipped.
6. Meeting 6 (8-9): Can be performed if Meeting 1 finished at 5.

• Total Meetings Scheduled (Naive Order): Only 2 meetings (Meeting 1 and Meeting 6). This is far below the maximum possible.

The Optimal Greedy Sequence (Sorted by End Time)

If we sort all meetings in ascending order of their end times, our sorted list looks like this:

Now, let's step through greedily:

1. Pick Meeting 3 (1-2): Room is empty. Schedule it. Free time becomes 2. Count = 1.
2. Check Meeting 2 (3-4): Start time 3 $\ge$ free time 2. Schedule it! Free time becomes 4. Count = 2. Order: [3, 2].
3. Check Meeting 1 (0-5): Start time 0 $<$ free time 4. Skip! (Too long, overlaps).
4. Check Meeting 5 (5-7): Start time 5 $\ge$ free time 4. Schedule it! Free time becomes 7. Count = 3. Order: [3, 2, 5].
5. Check Meeting 4 (5-9): Start time 5 $<$ free time 7. Skip!
6. Check Meeting 6 (8-9): Start time 8 $\ge$ free time 7. Schedule it! Free time becomes 9. Count = 4. Order: [3, 2, 5, 6].

• Total Maximum Meetings: 4 meetings (3 -> 2 -> 5 -> 6).

4. Step-by-Step Algorithm Walkthrough

To implement this programmatically, follow these structured steps:

1. Bundle Data: Create a custom data structure (or object/class) containing three attributes:
   • start: The meeting start time.
   • end: The meeting end time.
   • position: The original 1-based index (crucial if the interviewer asks for the meeting sequence order).
2. Populate Array: Transfer the input start and end arrays into an array of these custom data objects.
3. Sort by End Time: Sort the array in ascending order based on the end property. If end times are equal, standard sorting behavior handles it safely.
4. Initialize Trackers:
   • Set count = 1 (the first meeting in the sorted list can always be performed).
   • Set freeTime = sortedMeetings[0].end (the room becomes free when the first meeting ends).
   • Maintain a result list/vector containing sortedMeetings[0].position.
5. Iterate & Select: Loop from i = 1 to n - 1:
   • If sortedMeetings[i].start > freeTime, the meeting can be accommodated:
     • Increment count++.
     • Update freeTime = sortedMeetings[i].end.
     • Append sortedMeetings[i].position to our order tracking structure.
6. Return Output: Return count (or the order list, depending on the problem variant).

5. Complete Pseudocode / Code Architecture

Here is the robust structural implementation reflecting the algorithm design:

struct Meeting {
    int start;
    int end;
    int position;
};

class Solution {
public:
    int maxMeetings(vector<int>& start, vector<int>& end, int n) {
        // Step 1: Create an array of custom Meeting structures
        vector<Meeting> meetings(n);
        for(int i = 0; i < n; i++) {
            meetings[i].start = start[i];
            meetings[i].end = end[i];
            meetings[i].position = i + 1; // 1-based indexing
        }
        
        // Step 2: Sort meetings based on end time using a lambda comparator
        sort(meetings.begin(), meetings.end(), [](const Meeting& a, const Meeting& b) {
            return a.end < b.end;
        });
        
        // Step 3: Initialize tracking variables
        int count = 1;
        int freeTime = meetings[0].end;
        vector<int> executedOrder;
        executedOrder.push_back(meetings[0].position);
        
        // Step 4: Greedily iterate through remaining meetings
        for(int i = 1; i < n; i++) {
            if(meetings[i].start > freeTime) {
                count++;
                freeTime = meetings[i].end;
                executedOrder.push_back(meetings[i].position);
            }
        }
        
        // Optional: If you need to print or return the order, 'executedOrder' has it.
        return count;
    }
};

6. Time and Space Complexity Analysis

Understanding the operational efficiency of our greedy approach:

7. Real-World Practical Pitfalls & Edge Cases

When writing production-grade code or handling rigorous online judge tests, watch out for these subtle edge cases:

• Overlapping Exact Times (start == freeTime):
  • Pitfall: If Meeting A ends at time 4 and Meeting B starts at time 4, can Meeting B be performed?
  • Resolution: In standard meeting room problems, if a meeting ends at 4, the room is free at 4. Therefore, a meeting starting at 4 can use the room (start > freeTime vs start >= freeTime). Ensure your condition matches the specific platform's problem statement (usually strict greater-than > is expected unless instantaneous back-to-back occupancy is permitted).
• Unsorted Input Data:
  • Pitfall: Assuming input arrays start and end arrive pre-sorted. They rarely are. Always bundle indices and perform explicit sorting.
• Single Meeting Edge Case:
  • If $N = 1$, the loop is bypassed, count remains 1, and the code correctly returns 1 without out-of-bounds errors.

Summary and Key Takeaways

• Greedy Paradigm: The core strategy to maximize interval scheduling is sorting by earliest end time, preserving maximum future room availability.
• Data Bundling: Always encapsulate start, end, and original position into a unified object to support requirements asking for the chronological sequence order.
• Time Efficiency: Sorting dominates the runtime, bringing total time complexity to $O(N \log N)$.
• Linear Scan: Once sorted, a single $O(N)$ linear pass is sufficient to accumulate the maximum non-overlapping meeting count.
• Room Free-Time Tracker: Maintain a running freeTime variable updated continuously to the end time of each newly accepted meeting.