N meetings in one room

JavaView on GFG

Problem Overview

Maximum meetings in one room (activity selection).

See our study guide for structured GFG and LeetCode practice.

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?