Intervals
Sorting by end, and why that is the greedy choice
Keeping the interval that frees you up soonest is provably optimal, and the proof is worth knowing.
A different question needs a different key
Everything so far sorted by start, because the questions were about what connects to what. Now the question changes: given conflicting intervals, keep as many as possible without any two overlapping.
Sorting by start is actively bad here. A single very long interval that starts first would be kept and would block everything after it.
Why it works
Sort by end, keep greedily
Process intervals in order of increasing end. Keep an interval whenever it starts at or after the last kept interval's end.
The reason is an exchange argument, and it is short enough to give out loud. Suppose some optimal selection exists. Look at the interval in it that finishes earliest, and compare it to the one this algorithm picked first, which finishes no later. Swapping the optimal one for the algorithm's leaves the rest of the selection valid, because the replacement frees the resource at least as early. So there is an optimal selection containing the algorithm's first pick, and the argument repeats on what remains.
That is what makes it provably optimal rather than a heuristic that passes the samples.
The whole difference is which end you sort on, so here is the same set of intervals under both keys.
Tip
Why that example is the one to remember
One interval spans almost everything and two short ones fit inside it. Considered in end order, the two short ones come first, both survive, and the long one is rejected because it conflicts with what is already kept. Considered in start order, the long one is taken first and blocks both of the others, giving one instead of two.
Keep that shape in mind as the reason the key matters. If a greedy interval solution is producing answers that are too small, check whether it is sorting by the wrong end before checking anything else.
Key idea
Maximizing kept and minimizing removed
Some problems ask for the fewest intervals to delete so that no two of the rest overlap. That is the same problem: deleting the fewest means keeping the most, so the answer is the total count minus the greedy result.
Recognizing that a minimization is the complement of a maximization you already know is worth practicing. It comes up constantly and turns unfamiliar problems into solved ones.
Edge cases
Ties and the touching rule again
Sorting by end leaves ties among intervals that finish together. Any of them can be taken first without changing the count, since they all free the resource at the same moment.
The touching decision returns here. Comparing an interval's start against the last kept end with >= allows one to begin exactly when the previous ends. If the problem treats touching as a conflict, that becomes a strict comparison. Same decision, third appearance in this unit.
Cost of the greedy selection
The greedy selection is a sort followed by one pass that does constant work per interval. Give its time and space on n intervals, not counting the input itself.
Time
Space
Non Overlapping Intervals
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.