Sorting Intervals

Unsorted intervals hide the nearest competitor. If [8,10] appears before [1,3] and [2,6], a merge algorithm cannot know whether the current interval is final. Sorting establishes a direction so the next interval is the only new boundary that can affect the current decision.

After sorting, many interval problems become sweeps. You carry a current merged range, a chosen end boundary, or a room count, then update it with the next interval. The cost is usually O(n log n) for sorting, followed by an O(n) scan.

When the task is to merge, insert, or produce actual combined intervals, sort by start. This makes intervals arrive in the order they begin on the number line. For [1,3], [2,6], [8,10], the carried interval can only be extended by a later start; no unseen interval begins before 1 after the sort.

This is why Merge Intervals and Insert Interval use start order. The algorithm needs to know whether the next interval begins before the current carried interval ends. Sorting by end would lose the clean left boundary needed to emit merged ranges in order.

When the task is to keep as many non-overlapping intervals as possible, remove the fewest, or place the minimum number of arrows, sort by end. The greedy choice is usually to commit to the interval that finishes earliest because it leaves the most room for future intervals.

For example, with [1,10], [2,3], and [4,5], choosing the long interval first blocks two smaller compatible choices. Sorting by end considers [2,3] before [4,5], which is the structure behind Non-overlapping Intervals and Minimum Arrows to Burst Balloons.

You will often see Arrays.sort(intervals, (a, b) -> a[0] - b[0]) in examples. It is compact and works for small endpoint ranges, but subtraction can overflow when values are near integer limits. Overflow can reverse the ordering and make the sweep silently wrong.

Prefer Integer.compare(a[0], b[0]) for start order and Integer.compare(a[1], b[1]) for end order. If ties matter, add a secondary comparison deliberately, such as sorting by start then end. A comparator is not just syntax; it defines the geometry your algorithm will see.