Problem: Meeting Rooms (Interval Scheduling)

Problem Statement

Given a list of meeting intervals [start, end], find the maximum number of meetings one person can attend, assuming they can only be in one meeting at a time.

Approach: Earliest Finish Time First

This is the optimal greedy strategy for interval scheduling.

1. Sort: Sort all meetings by their End Time.
   • Why? Finishing a meeting as early as possible leaves the most time remaining for other meetings.
2. Iterate:
   • Pick the first meeting (the one that ends earliest).
   • For the next meeting, if its start >= last_end_time, attend it and update last_end_time.

Java Implementation

public int maxMeetings(int[][] intervals) {
    if (intervals.length == 0) return 0;
    
    // Sort by end time
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

    int count = 1;
    int lastEnd = intervals[0][1];

    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= lastEnd) {
            count++;
            lastEnd = intervals[i][1];
        }
    }
    return count;
}

Complexity Analysis

• Time Complexity: $O(n \log n)$ due to sorting. The scan is $O(n)$.
• Space Complexity: $O(1)$ (or $O(\log n)$ depending on sorting implementation).

Interview Tips

• Always justify the sort order. "Sorting by start time doesn't work because a very long meeting starting early could block many shorter ones."