GreedyProblem 14 of 35

Find maximum meetings in one room

Brute Force
Time: O(n^2)
Space: O(n)
Optimal
Time: O(n log n)
Space: O(n)

Problem Statement

Given start and end times of n meetings, find the maximum number of meetings that can be held in a single meeting room. Only one meeting can be held at a time in the room.

Constraints:

  • 1 ≤ n ≤ 10^5
  • 0 ≤ start[i] < end[i] ≤ 10^6

Example:

  • Input: start = [1, 3, 0, 5, 8, 5], end = [2, 4, 6, 7, 9, 9]
  • Output: 4
  • Explanation: Meetings 1, 2, 4, 5 can be held (indices 0, 1, 3, 4 if 0-indexed).

Example 2:

  • Input: start = [75250, 50074, 43659, 8931, 11273, 27545, 50879, 77924] end = [112960, 114515, 81825, 93424, 54316, 35533, 73383, 160252]
  • Output: 3

Approach 1: Brute Force (Check All Combinations)

Intuition

Try all possible subsets of meetings and find the largest subset where no two meetings overlap.

Algorithm

  1. Generate all possible subsets of meetings
  2. For each subset, check if all meetings are non-overlapping
  3. Track maximum size of valid subsets
  4. Return the meetings in that subset
java
import java.util.*;

public class Solution {
    private int maxMeetings = 0;
    private List<Integer> bestSubset = new ArrayList<>();
    
    private boolean isValid(int[][] meetings, List<Integer> subset) {
        if (subset.isEmpty()) return true;
        
        List<Integer> sorted = new ArrayList<>(subset);
        sorted.sort((a, b) -> meetings[a][1] - meetings[b][1]);
        
        for (int i = 1; i < sorted.size(); i++) {
            int prev = sorted.get(i - 1);
            int curr = sorted.get(i);
            if (meetings[curr][0] < meetings[prev][1]) {
                return false;
            }
        }
        return true;
    }
    
    private void solve(int[][] meetings, int idx, List<Integer> current) {
        if (isValid(meetings, current) && current.size() > maxMeetings) {
            maxMeetings = current.size();
            bestSubset = new ArrayList<>(current);
        }
        
        if (idx == meetings.length) return;
        
        current.add(idx);
        solve(meetings, idx + 1, current);
        current.remove(current.size() - 1);
        
        solve(meetings, idx + 1, current);
    }
    
    public int findMaxMeetings(int[] start, int[] end) {
        int n = start.length;
        int[][] meetings = new int[n][3];
        for (int i = 0; i < n; i++) {
            meetings[i] = new int[]{start[i], end[i], i + 1};
        }
        
        maxMeetings = 0;
        solve(meetings, 0, new ArrayList<>());
        return maxMeetings;
    }
}

Complexity Analysis

  • Time Complexity: O(2^n * n^2) - 2^n subsets, O(n log n + n) per validation
  • Space Complexity: O(n) - For storing subsets

Approach 2: Greedy (Sort by End Time) - Optimal

Intuition

This is the classic Activity Selection Problem. Sort meetings by end time and greedily select meetings that don't conflict with previously selected ones.

Key Insight: Selecting the meeting that ends earliest leaves maximum room for subsequent meetings.

Algorithm

  1. Create meeting tuples with (start, end, original_index)
  2. Sort by end time
  3. Select first meeting
  4. For each subsequent meeting, if it starts after last selected ends, select it
  5. Return count and selected meeting indices
java
import java.util.*;

public class MaxMeetings {
    
    public List<Integer> findMaxMeetings(int[] start, int[] end) {
        int n = start.length;
        
        // Create meetings array: [end, start, index]
        int[][] meetings = new int[n][3];
        for (int i = 0; i < n; i++) {
            meetings[i][0] = end[i];
            meetings[i][1] = start[i];
            meetings[i][2] = i + 1;  // 1-indexed
        }
        
        // Sort by end time
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);
        
        List<Integer> selected = new ArrayList<>();
        int lastEndTime = -1;
        
        for (int[] meeting : meetings) {
            int endTime = meeting[0];
            int startTime = meeting[1];
            int idx = meeting[2];
            
            if (startTime > lastEndTime) {
                selected.add(idx);
                lastEndTime = endTime;
            }
        }
        
        return selected;
    }
    
    public int maxMeetingsCount(int[] start, int[] end) {
        return findMaxMeetings(start, end).size();
    }
    
    public static void main(String[] args) {
        MaxMeetings mm = new MaxMeetings();
        
        int[] start = {1, 3, 0, 5, 8, 5};
        int[] end = {2, 4, 6, 7, 9, 9};
        
        List<Integer> selected = mm.findMaxMeetings(start, end);
        
        System.out.println("Maximum meetings: " + selected.size());
        System.out.println("Selected meetings: " + selected);
    }
}

Dry Run Example

start = [1, 3, 0, 5, 8, 5] end = [2, 4, 6, 7, 9, 9] Original meetings: Meeting 1: 1 - 2 Meeting 2: 3 - 4 Meeting 3: 0 - 6 Meeting 4: 5 - 7 Meeting 5: 8 - 9 Meeting 6: 5 - 9 Sorted by end time: Meeting 1: 1 - 2 (end=2) Meeting 2: 3 - 4 (end=4) Meeting 3: 0 - 6 (end=6) Meeting 4: 5 - 7 (end=7) Meeting 5: 8 - 9 (end=9) Meeting 6: 5 - 9 (end=9) Selection process: lastEnd = -1 Step 1: Meeting 1 (1-2) start=1 > lastEnd=-1? YES SELECT! lastEnd = 2 selected = [1] Step 2: Meeting 2 (3-4) start=3 > lastEnd=2? YES SELECT! lastEnd = 4 selected = [1, 2] Step 3: Meeting 3 (0-6) start=0 > lastEnd=4? NO SKIP Step 4: Meeting 4 (5-7) start=5 > lastEnd=4? YES SELECT! lastEnd = 7 selected = [1, 2, 4] Step 5: Meeting 5 (8-9) start=8 > lastEnd=7? YES SELECT! lastEnd = 9 selected = [1, 2, 4, 5] Step 6: Meeting 6 (5-9) start=5 > lastEnd=9? NO SKIP Result: Maximum meetings = 4 Selected meetings: [1, 2, 4, 5] Timeline visualization: Time: 0 1 2 3 4 5 6 7 8 9 M1: [--] ← Selected M2: [--] ← Selected M3: [--------] ← Overlaps with M1, M2 M4: [--] ← Selected M5: [--] ← Selected M6: [------] ← Overlaps with M4, M5

Complexity Analysis

  • Time Complexity: O(n log n) - Dominated by sorting
  • Space Complexity: O(n) - For storing meetings with indices

Why Greedy Works

Proof by Exchange Argument:

  1. Let OPT be any optimal solution
  2. Let GREEDY be our greedy solution
  3. If first meeting differs, swap OPT's first meeting with greedy's choice
  4. Greedy's choice ends earlier, so it can't cause more conflicts
  5. The swap doesn't reduce the number of meetings
  6. By induction, greedy solution is optimal

Key Takeaways

  1. Sort by End Time: The key greedy strategy
  2. Earliest Finish First: Select meeting that ends soonest
  3. Non-overlapping Check: Next meeting must start after last selected ends
  4. Classic Problem: Foundation for many scheduling problems
  5. 1-indexed Output: Problem often asks for 1-indexed meeting numbers
  6. Tie Breaking: When end times are equal, any order works
  7. Similar Problems: Activity Selection, Non-overlapping Intervals
Previous
Check if it is possible to survive on Island
Next
Maximum product subset of an array