☕ DSA Java Articles

Topics › Greedy Algorithms › Medium/Hard

N meetings in one room

Medium TUF ID 549 A2ZSDE

Java source ↗ Edit this article ↗

Problem

There is one meeting room and n meeting requests. Meeting i (numbered from 1) runs from start[i] to end[i]. Only one meeting can be in the room at a time, and a chosen meeting must start strictly after the previous chosen meeting ends: if one meeting ends at time 20, the next may not start at 20. Find the maximum number of meetings that can be held, and list the chosen meetings in the order they take place.

This is the classic activity selection problem. The GeeksforGeeks version only asks for the count; Striver’s version also prints the order, so the optimal method here returns the list and its size is the count.

Constraints: 1 ≤ n ≤ 10^5, 0 ≤ start[i] ≤ end[i] ≤ 10^6.

Example 1

start = [1, 3, 0, 5, 8, 5], end = [2, 4, 5, 7, 9, 9]
answer = 4, order 1 2 4 5     // (1,2) (3,4) (5,7) (8,9) never overlap

Example 2

start = [10, 12, 20], end = [20, 25, 30]
answer = 1, order 1           // meeting 3 starts at 20, the same moment meeting 1 ends, which is a clash

Approach 1: Brute force, every subset

Intuition. The answer is the largest set of meetings in which no two overlap, so try every set. A set is valid if, after sorting its meetings by start time, each meeting starts strictly after the previous one ends. Because every meeting satisfies start ≤ end, checking neighbours in start order is enough: if each consecutive pair is clean, the meetings form a chain and no two can overlap.

Algorithm.

  1. For every bitmask from 0 to 2^n - 1, collect the meetings whose bits are set.
  2. Skip the set if it is not larger than the best found so far.
  3. Sort the set by start time and check start[next] > end[previous] for every consecutive pair.
  4. If the set is valid, record its size.
static int bruteForce(int[] start, int[] end) {
    int n = start.length, best = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        List<Integer> chosen = new ArrayList<>();
        for (int i = 0; i < n; i++) if ((mask & (1 << i)) != 0) chosen.add(i);
        if (chosen.size() <= best) continue;          // cannot improve the answer
        chosen.sort((a, b) -> Integer.compare(start[a], start[b]));
        boolean ok = true;
        for (int k = 1; k < chosen.size() && ok; k++) {
            if (start[chosen.get(k)] <= end[chosen.get(k - 1)]) ok = false;   // clash with the previous meeting
        }
        if (ok) best = chosen.size();
    }
    return best;
}

Complexity. Time O(2^n · n log n): 2^n subsets, each sorted and scanned. Space O(n) for the current subset. Only feasible for about 20 meetings; it serves as a correctness reference.

Approach 2: Optimal, earliest finishing meeting first

Intuition. Which meeting should go first? Not the earliest starting one: a meeting (0, 100) starts first and blocks everything. Not the shortest one either: with (0, 5), (6, 10) and a short (4, 7), picking the short meeting kills both others. The right choice is the meeting that ends earliest, because it leaves the room free as soon as possible for whatever comes next.

Why this is safe (the exchange argument): let g be the meeting with the smallest end time. Take any optimal schedule and let f be its first meeting. Then end[g] ≤ end[f]. Replace f with g: g finishes no later than f did, so it still finishes before the schedule’s second meeting starts. The new schedule has the same size and starts with g. After committing to g, what remains is the same problem restricted to meetings that start after end[g], and the same argument applies again. So repeatedly taking the earliest-ending compatible meeting is optimal.

In code this becomes a single sorted sweep: sort meetings by end time and take each one whose start is strictly after the end of the last one taken.

Algorithm.

  1. Sort meeting indices by end time; on equal end times, put the lower meeting number first so the printed order is deterministic.
  2. Set lastEnd to a value smaller than any time.
  3. For each meeting in that order, if start[i] > lastEnd, take it (record i + 1) and set lastEnd = end[i].
  4. Return the list of taken meetings; its size is the answer.
static List<Integer> optimal(int[] start, int[] end) {
    int n = start.length;
    Integer[] order = new Integer[n];
    for (int i = 0; i < n; i++) order[i] = i;
    // earliest finish first; on equal end times the lower meeting number goes first
    Arrays.sort(order, (a, b) -> end[a] != end[b] ? Integer.compare(end[a], end[b]) : Integer.compare(a, b));
    List<Integer> picked = new ArrayList<>();
    long lastEnd = Long.MIN_VALUE;
    for (int i : order) {
        if (start[i] > lastEnd) {
            picked.add(i + 1);                       // meetings are numbered from 1
            lastEnd = end[i];
        }
    }
    return picked;
}

lastEnd is a long initialised to Long.MIN_VALUE, so the very first meeting is always accepted without a special case, even if a meeting could start at time 0 or a negative time. Comparing an int start with a long is a normal widening comparison.

Dry run on Example 1. Sorted by end time the meetings are 1 (1,2), 2 (3,4), 3 (0,5), 4 (5,7), 5 (8,9), 6 (5,9).

meeting start end start > lastEnd? lastEnd after
1 1 2 yes, nothing chosen yet 2
2 3 4 3 > 2, yes 4
3 0 5 0 > 4, no 4
4 5 7 5 > 4, yes 7
5 8 9 8 > 7, yes 9
6 5 9 5 > 9, no 9

The chosen order is 1 2 4 5, so the answer is 4.

Complexity. Time O(n log n) for sorting; the sweep is O(n). Space O(n) for the index array and the result list.

Edge cases and pitfalls