Find maximum meetings in one room

The problem, simply

There is one meeting room and n meetings. Meeting i runs from start[i] to end[i]. Only one meeting can use the room at a time.

Pick the most meetings you can, and give back their numbers (counting from 1) in increasing order. In this version a meeting cannot start at the exact moment the previous one ends: the next start must be strictly bigger than the last end, because the room needs a moment to be cleaned.

A story to remember it

Picture it

Examples

Way 1: the simple way

Think of it as building the longest chain of meetings, where each one starts after the previous one ends.

1. Sort the meetings by end time, so any meeting that can come before i sits earlier in the list.
2. For each meeting i, chain[i] is the longest chain that ends with meeting i. It is 1 plus the best chain[j] over all earlier meetings j that end before i starts.
3. The biggest chain[i] is the answer. To get the meeting numbers, remember which j each meeting came from and follow those links back.

class Solution {
    public List<Integer> maxMeetings(int[] start, int[] end) {
        int n = start.length;
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> Integer.compare(end[a], end[b])); // ties keep input order

        int[] chain = new int[n];
        int[] from = new int[n];
        int bestAt = 0;
        for (int x = 0; x < n; x++) {
            int i = order[x];
            chain[x] = 1;
            from[x] = -1;
            for (int y = 0; y < x; y++) {           // every earlier meeting
                int j = order[y];
                if (end[j] < start[i] && chain[y] + 1 > chain[x]) {
                    chain[x] = chain[y] + 1;
                    from[x] = y;
                }
            }
            if (chain[x] > chain[bestAt]) bestAt = x;
        }

        List<Integer> picked = new ArrayList<>();
        for (int x = bestAt; x != -1 && n > 0; x = from[x]) picked.add(order[x] + 1);
        Collections.sort(picked);
        return picked;
    }
}

How long it takes: every meeting looks back at every earlier one, O(n^2). Extra room: the chain and from arrays, O(n).

Way 2: the clever way

Do what the teacher does.

1. Sort the meetings by end time. If two end together, the smaller number goes first.
2. Keep freeAfter, the end of the last booked meeting. Start it below every time.
3. Walk the sorted meetings. If a meeting starts strictly after freeAfter, book it and move freeAfter to its end. Otherwise skip it.
4. Sort the booked meeting numbers and return them.

The meeting that ends first is always safe to take. In any best plan, swap its first meeting for this one: it ends no later, so every later meeting still fits.

class Solution {
    public List<Integer> maxMeetings(int[] start, int[] end) {
        int n = start.length;
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;
        // earliest end first; on a tie the smaller number 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 freeAfter = Long.MIN_VALUE;
        for (int i : order) {
            if (start[i] > freeAfter) {   // strictly after: the room needs a moment
                picked.add(i + 1);
                freeAfter = end[i];
            }
        }
        Collections.sort(picked);
        return picked;
    }
}

How long it takes: sorting is O(n log n), the walk is O(n), so O(n log n). Extra room: the order array and the answer, O(n).

Watch out for

• Sorting by start time or by length gives wrong answers. Only end time works.
• The output wants meeting numbers from 1, sorted. Keep the original index before sorting.
• Times can be large. Compare with Integer.compare, not by subtracting.
• freeAfter must start below every start time, or a meeting at time 0 gets skipped.

What interviewers ask next

• How many rooms are needed to hold every meeting? Sort by start, keep a min heap of end times, reuse a room when the smallest end is before the new start. The largest heap size is the answer (Meeting Rooms II).
• Can one person attend all meetings? Sort by start and check that no meeting starts before the previous one ends.
• What if meetings have priorities and you want the most total priority? That is weighted interval scheduling: sort by end, then dynamic programming with binary search, O(n log n).
• Why does the greedy beat the chain method? The chain method checks every earlier meeting. The greedy proves it only ever needs the one that ended first, so one pass is enough.

Remember this

Grown-up words: the reading corner is a single shared resource, booking groups is interval scheduling, "leaves first" is the earliest finish time rule, and the chain method is a longest chain dynamic program.