Given a list of meetings with start and end times, pick the largest set of them that do not overlap.

Two sort keys that look reasonable and are not

The instinct is to sort by start time and take greedily from the front. It fails on three meetings: one from 1 to 20, one from 2 to 3, and one from 4 to 5. Earliest start takes the long meeting first, blocks both others, and returns one. The optimum takes the two short ones and returns two. The problem is that a meeting's start says nothing about how much of the day it consumes.

The obvious correction is to sort by duration and take the shortest first, on the theory that a short meeting blocks least. That fails too, on one from 1 to 10, one from 9 to 12, and one from 11 to 20. The shortest is 9 to 12, three units long. Taking it blocks both the others, since it overlaps 1 to 10 and it overlaps 11 to 20, so the answer is one. Taking 1 to 10 and 11 to 20 gives two. A short meeting placed across a seam does more damage than a long one placed at the edge.

Working through both of those, out loud, before you write any code is most of the credit on this question. A candidate who states the correct rule immediately has demonstrated recall; a candidate who eliminates two plausible rules by construction has demonstrated the thing the rule is for.

Why earliest finishing time is provably safe

Sort by end time and take each meeting whose start is not before the end of the last one taken. The claim is that this is optimal, and the proof is an exchange argument short enough to give in an interview.

Let the meeting with the earliest finishing time be f, and let S be any optimal solution. If S contains f, the greedy's first choice agrees with an optimum and we recurse on what remains after f. If S does not contain f, look at the meeting g in S that finishes earliest. Because f finishes no later than g, replacing g with f in S cannot introduce a conflict: everything else in S starts at or after g's end, which is at or after f's end. So S with f substituted for g is still conflict-free and still the same size, and it is therefore also optimal. Either way there is an optimal solution containing f.

Having fixed f, every remaining meeting that overlaps f is unusable in any solution containing f, and the subproblem over the rest is the same problem on a smaller set. Induction finishes it. What makes earliest finish the right key is exactly what the argument used: finishing earliest leaves the largest possible remaining interval, and the number of meetings you can fit in the rest depends only on how much of the timeline is left.

The meeting that ends when the next begins

Ask the boundary question before you write the comparison. If a meeting runs 9 to 10 and another runs 10 to 11, do they conflict? Under the half-open convention, which is what calendars use, they do not, and the test is that the next start is greater than or equal to the last end. Under a closed convention they do, and the test becomes strictly greater.

This single character decides the answer on adjacent inputs, and it is the most common source of a silently wrong result here, because a test suite of randomly generated intervals will rarely produce an exact touch. Say which convention you are assuming and put it in the comment.

int maxNonOverlapping(int[][] meetings) {
    Arrays.sort(meetings, Comparator.comparingInt(m -> m[1]));   // by finish time
    int taken = 0;
    int lastEnd = Integer.MIN_VALUE;
    for (int[] m : meetings) {
        if (m[0] >= lastEnd) {      // half-open: ending at 10 frees the slot starting at 10
            taken++;
            lastEnd = m[1];
        }
    }
    return taken;
}

The cost is dominated by the sort, so O of n log n time and O of 1 extra space beyond whatever the sort needs. The scan itself is linear and touches each meeting once.

What this greedy stops solving

The moment the objective changes from counting meetings to maximising something else, the exchange argument stops working, and knowing where the boundary is matters more than the code.

Attach a value to each meeting and ask for the greatest total value. Earliest finish is now wrong for the obvious reason: a single high-value meeting can be worth more than three cheap ones, and no local rule sees that. The weighted version is solved by dynamic programming over meetings sorted by finish time, where each meeting either is taken, in which case you add its value to the best answer among meetings finishing at or before its start, or is not. Finding that predecessor by binary search keeps it at O of n log n.

The other direction is more rooms rather than more objectives, which turns into a different problem entirely: the minimum number of rooms needed to hold everything is a question about maximum concurrency and is answered by sweeping endpoints, not by selecting a subset. Candidates who conflate the two, and try to solve the room-count question by repeatedly running this greedy, are answering a question that was not asked.