hard

Sort Intervals by Start (Stable Selection Sort)

Sort a list of intervals by start time using a stable selection sort variant.

1. Define the problem

Sort Intervals by Start (Stable Selection Sort)

Given an array of intervals where each interval is [start, end], sort them by start value in ascending order. When two intervals share the same start, keep their original relative order (a stable sort). A plain selection sort swaps the minimum directly into place, which can jump it past an equal-valued interval and break that guarantee. Instead, shift every interval between the old and new positions over by one instead of swapping, so equal starts never change order. Return the sorted array.

Constraints

  • 1 ≤ intervals.length ≤ 500
  • 0 ≤ intervalsi[0] ≤ intervalsi[1] ≤ 104

Example

Inputintervals = [[3, 4], [1, 2], [1, 5], [2, 3]]
Output[[1, 2], [1, 5], [2, 3], [3, 4]]

Explanation Both intervals starting at 1 keep their original order — [1, 2] stays before [1, 5] because it appeared first in the input.

2. Know the words first

In plain terms

Stable sort
A sort where elements that compare equal keep the same relative order they had before sorting.
Shift (instead of swap)
Moving the found minimum into place by sliding every element in between forward one slot, rather than trading places directly with one other element.
3. Visualize the solution

Find the minimum start, then shift it into place — never swap

Find the minimum start, then shift it into place — never swap
Statuspass 1

Scan all 4 intervals — the smallest start is 1, first seen at index 1 ([1, 2]).

What happens in this step

intervals = [[3,4], [1,2], [1,5], [2,3]], sortedEnd = 0, min start so far = 3 (index 0, [3,4])

  idx 1: [1,2] start 1 < 3  →  new min = [1,2] at index 1
  idx 2: [1,5] start 1 < 1  →  no (tie — index 1 found first, keeps priority)
  idx 3: [2,3] start 2 < 1  →  no

[1,2] wins with the strictly-earlier tie-break rule: the first index with the smallest start is kept.
Step 1 of 5

Steps to visualize

  1. Scan the unsorted region for the interval with the smallest start value, preferring the earliest one found on ties.
  2. Remove that interval and shift every interval between its old spot and sortedEnd forward by one.
  3. Insert the minimum at index sortedEnd — every interval it passed keeps its original relative order.
  4. Move sortedEnd forward and repeat.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Find the minimum start, then shift it into place — never swap
Statuspass 1

Scan all 4 intervals — the smallest start is 1, first seen at index 1 ([1, 2]).

What happens in this step

intervals = [[3,4], [1,2], [1,5], [2,3]], sortedEnd = 0, min start so far = 3 (index 0, [3,4])

  idx 1: [1,2] start 1 < 3  →  new min = [1,2] at index 1
  idx 2: [1,5] start 1 < 1  →  no (tie — index 1 found first, keeps priority)
  idx 3: [2,3] start 2 < 1  →  no

[1,2] wins with the strictly-earlier tie-break rule: the first index with the smallest start is kept.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function sortIntervalsStable(intervals) {
  const arr = intervals.map((interval) => interval.slice());

  for (let sortedEnd = 0; sortedEnd < arr.length - 1; sortedEnd++) {
    let minIndex = sortedEnd;

    for (let scan = sortedEnd + 1; scan < arr.length; scan++) {
      if (arr[scan][0] < arr[minIndex][0]) {
        minIndex = scan;
      }
    }

    if (minIndex !== sortedEnd) {
      const minInterval = arr[minIndex];

      for (let shift = minIndex; shift > sortedEnd; shift--) {
        arr[shift] = arr[shift - 1];
      }

      arr[sortedEnd] = minInterval;
    }
  }

  return arr;
}
Time
O(n^2)
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
intervals = [[3, 4], [1, 2], [1, 5], [2, 3]][[1, 2], [1, 5], [2, 3], [3, 4]]example from the docstring
intervals = [[1, 2], [2, 3], [3, 4]][[1, 2], [2, 3], [3, 4]]already sorted with no duplicate starts
intervals = [[5, 6], [5, 1], [5, 9]][[5, 6], [5, 1], [5, 9]]every interval shares the same start, order must be fully preserved
intervals = [[3, 1], [2, 1], [1, 1]][[1, 1], [2, 1], [3, 1]]distinct starts in fully reverse order
intervals = [[4, 8]][[4, 8]]smallest valid input, a single interval
intervals = [[2, 5], [2, 1]][[2, 5], [2, 1]]two intervals tied on start keep their original order
intervals = [[4, 1], [1, 9], [4, 2], [1, 3]][[1, 9], [1, 3], [4, 1], [4, 2]]two tied groups that must each preserve their own relative order

Keep reading