N meetings in one room

JavaView on GFG

Intuition

Maximum meetings in one room (activity selection). Greedy: sort by end time, greedily pick non-overlapping.

Algorithm

1Sort by end time. Track last end. For each meeting: if start > last end: select, update last end.

Common Pitfalls

•Classic interval scheduling. Sort by end, not start. O(n log n). Same as LC 435 complement.

N meetings in one room.java

Java

// Approach: Sort meetings by end time. Greedily select meetings whose start time >= last selected end time.
// Time: O(n log n) Space: O(n)
import java.util.*;

class Solution {
    // Function to find the maximum number of meetings that can
    // be performed in a meeting room.
    public int maxMeetings(int n, int start[], int end[]) {
        int[][] ans = new int[n][2];

        for (int i = 0; i < n; i++) {
            ans[i][0] = start[i];
            ans[i][1] = end[i];
        }

        Arrays.sort(ans, (a, b) -> a[1] - b[1]);

        int cnt = 0;
        int endTime = ans[0][1];

        for (int i = 1; i < n; i++) {
            if (ans[i][0] <= endTime)
                continue;
            else {
                cnt++;
                endTime = ans[i][1];
            }
        }

        return cnt + 1;
    }
}

Was this solution helpful?