Intervals · Commitwise

Meetings in a calendar, booked hotel nights, a video’s buffered ranges, the hours a shop is open: all of them are intervals, a start and an end. Interval problems look varied, but almost all of them start the same way: sort by start (or by end), then walk through once. After the sort, the only question left is how two neighboring intervals relate.

New to some of these? Open what you need, or skip ahead.

Basics:What are arrays and indexes?

An array is a row of values stored one after another: [5, 8, 2, 9]. Each position has an index, starting at 0: here 5 is at index 0 and 9 at index 3. The last index is always count - 1 (Swift) or size - 1 / length - 1 (Kotlin, Java, TypeScript).

Reading nums[2] is instant, whatever the array’s size. Reading an index that doesn’t exist (like nums[4] here) crashes with an “index out of range” error (in TypeScript it quietly gives undefined, a bug of its own), which is why loops usually go from 0 up to, but not including, the length.

Basics:How does sorting work in each language?

Every language has a built-in sort that takes O(n log n):

Swift: nums.sort() sorts in place; nums.sorted() returns a sorted copy; sorted(by: >) sorts descending.
Kotlin: nums.sort() in place; nums.sorted() returns a copy; sortedBy { it.end } sorts by a property.
Java: Arrays.sort(nums) for arrays, list.sort(Comparator.comparingInt(Meeting::end)) for lists.
TypeScript: nums.sort((a, b) => a - b). Without the comparator, numbers are sorted as text, so 10 comes before 9.

Basics:What does O(n) mean?

Big-O describes how the amount of work grows with the size of the input n:

O(1): the same work whatever the size (reading array[5]).
O(log n): grows very slowly (about 20 steps for a million items).
O(n): grows in step with the input (one pass over the array).
O(n²): comparing every item with every other item, which gets slow fast.

You’ll see it next to every solution, for time and for extra space (memory). The Big-O tutorial explains it properly.

Part Not started

Overlaps and merging

Picture a row of booked meetings drawn as bars on a timeline. Two bars overlap if they share any time. If you sort the bars by their start time, something useful happens: a bar can only overlap the bars just before it, never one far back that already ended. So you only ever compare a bar with the latest one you’ve kept.

Interval problems reduce to two decisions: the order (by start for merging and covering, by end for selecting non-overlapping ones) and the boundary convention (closed [a, b], where [1, 4] and [4, 5] overlap, or half-open [a, b), where back-to-back meetings don’t). Clarify the second one out loud; it changes < to <= in every comparison, and it’s the source of most wrong answers.

Two intervals a and b overlap when each one starts before the other ends: a.start <= b.end && b.start <= a.end (with < if touching ends don’t count). Once the list is sorted by start, that simplifies to one check against the last kept interval: does the current one start before the last one ends?

Merge Intervals. Merge all overlapping intervals. [[1, 3], [2, 6], [8, 10], [15, 18]] → [[1, 6], [8, 10], [15, 18]]. [[1, 4], [4, 5]] → [[1, 5]].

Sort by start, then extend or append

func merge(_ intervals: [[Int]]) -> [[Int]] {
    let sorted = intervals.sorted { $0[0] < $1[0] }
    var merged: [[Int]] = []
    for interval in sorted {
        if let last = merged.last, interval[0] <= last[1] {
            merged[merged.count - 1][1] = max(last[1], interval[1])   // overlaps: extend
        } else {
            merged.append(interval)                                   // gap: start a new one
        }
    }
    return merged
}

fun merge(intervals: Array<IntArray>): Array<IntArray> {
    val sorted = intervals.sortedBy { it[0] }
    val merged = mutableListOf<IntArray>()
    for (interval in sorted) {
        val last = merged.lastOrNull()
        if (last != null && interval[0] <= last[1]) {
            last[1] = maxOf(last[1], interval[1])     // overlaps: extend
        } else {
            merged.add(interval.copyOf())             // gap: start a new one
        }
    }
    return merged.toTypedArray()
}

int[][] merge(int[][] intervals) {
    int[][] sorted = intervals.clone();
    Arrays.sort(sorted, Comparator.comparingInt(a -> a[0]));
    List<int[]> merged = new ArrayList<>();
    for (int[] interval : sorted) {
        int[] last = merged.isEmpty() ? null : merged.get(merged.size() - 1);
        if (last != null && interval[0] <= last[1]) {
            last[1] = Math.max(last[1], interval[1]);   // overlaps: extend
        } else {
            merged.add(interval.clone());               // gap: start a new one
        }
    }
    return merged.toArray(new int[0][]);
}

function merge(intervals: number[][]): number[][] {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const merged: number[][] = [];
  for (const [start, end] of sorted) {
    const last = merged[merged.length - 1];
    if (last && start <= last[1]) {
      last[1] = Math.max(last[1], end);             // overlaps: extend
    } else {
      merged.push([start, end]);                    // gap: start a new one
    }
  }
  return merged;
}

The sort is O(n log n), and the loop looks at each interval once, so the whole thing is O(n log n). Notice the copies (copyOf, clone, a new array in TypeScript): the code changes last[1] in place, and without a copy it would also change the caller’s input.

Spot the bugMerging that loses time

Tap the line with the bug.

func merge(_ intervals: [[Int]]) -> [[Int]] {
    let sorted = intervals.sorted { $0[0] < $1[0] }
    var merged: [[Int]] = []
    for interval in sorted {
        if let last = merged.last, interval[0] <= last[1] {
            merged[merged.count - 1][1] = interval[1]
        } else {
            merged.append(interval)
        }
    }
    return merged
}

fun merge(intervals: Array<IntArray>): Array<IntArray> {
    val sorted = intervals.sortedBy { it[0] }
    val merged = mutableListOf<IntArray>()
    for (interval in sorted) {
        val last = merged.lastOrNull()
        if (last != null && interval[0] <= last[1]) {
            last[1] = interval[1]
        } else {
            merged.add(interval.copyOf())
        }
    }
    return merged.toTypedArray()
}

int[][] merge(int[][] intervals) {
    int[][] sorted = intervals.clone();
    Arrays.sort(sorted, Comparator.comparingInt(a -> a[0]));
    List<int[]> merged = new ArrayList<>();
    for (int[] interval : sorted) {
        int[] last = merged.isEmpty() ? null : merged.get(merged.size() - 1);
        if (last != null && interval[0] <= last[1]) {
            last[1] = interval[1];
        } else {
            merged.add(interval.clone());
        }
    }
    return merged.toArray(new int[0][]);
}

function merge(intervals: number[][]): number[][] {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const merged: number[][] = [];
  for (const [start, end] of sorted) {
    const last = merged[merged.length - 1];
    if (last && start <= last[1]) {
      last[1] = end;
    } else {
      merged.push([start, end]);
    }
  }
  return merged;
}

Exercisemedium

Insert Interval

intervals is sorted by start and has no overlaps. Insert newInterval, merging where needed, and return the result, still sorted and without overlaps. Do it in O(n), without sorting again.

intervals = [[1, 3], [6, 9]],                     new = [2, 5]  → [[1, 5], [6, 9]]
intervals = [[1, 2], [3, 5], [6, 7], [8, 10]],    new = [4, 8]  → [[1, 2], [3, 10]]

›

The list falls into three groups: intervals that end before the new one starts, intervals that overlap it, and intervals that start after it ends.

›

Copy the first group as is. For the second, grow the new interval: start = min of the starts, end = max of the ends. Add it, then copy the third group.

SolutionTry it yourself firstTime O(n)Space O(n) for the result

func insert(_ intervals: [[Int]], _ newInterval: [Int]) -> [[Int]] {
    var result: [[Int]] = []
    var current = newInterval
    var i = 0
    while i < intervals.count && intervals[i][1] < current[0] {      // ends before: keep
        result.append(intervals[i]); i += 1
    }
    while i < intervals.count && intervals[i][0] <= current[1] {     // overlaps: absorb
        current = [min(current[0], intervals[i][0]), max(current[1], intervals[i][1])]
        i += 1
    }
    result.append(current)
    result.append(contentsOf: intervals[i...])                        // starts after: keep
    return result
}

fun insert(intervals: Array<IntArray>, newInterval: IntArray): Array<IntArray> {
    val result = mutableListOf<IntArray>()
    var start = newInterval[0]; var end = newInterval[1]
    var i = 0
    while (i < intervals.size && intervals[i][1] < start) result.add(intervals[i++])   // ends before
    while (i < intervals.size && intervals[i][0] <= end) {                            // overlaps
        start = minOf(start, intervals[i][0])
        end = maxOf(end, intervals[i][1])
        i++
    }
    result.add(intArrayOf(start, end))
    while (i < intervals.size) result.add(intervals[i++])                             // starts after
    return result.toTypedArray()
}

int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> result = new ArrayList<>();
    int start = newInterval[0], end = newInterval[1];
    int i = 0;
    while (i < intervals.length && intervals[i][1] < start) result.add(intervals[i++]);   // ends before
    while (i < intervals.length && intervals[i][0] <= end) {                             // overlaps
        start = Math.min(start, intervals[i][0]);
        end = Math.max(end, intervals[i][1]);
        i++;
    }
    result.add(new int[] { start, end });
    while (i < intervals.length) result.add(intervals[i++]);                             // starts after
    return result.toArray(new int[0][]);
}

function insert(intervals: number[][], newInterval: number[]): number[][] {
  const result: number[][] = [];
  let [start, end] = newInterval;
  let i = 0;
  while (i < intervals.length && intervals[i][1] < start) result.push(intervals[i++]);   // ends before
  while (i < intervals.length && intervals[i][0] <= end) {                              // overlaps
    start = Math.min(start, intervals[i][0]);
    end = Math.max(end, intervals[i][1]);
    i++;
  }
  result.push([start, end]);
  while (i < intervals.length) result.push(intervals[i++]);                             // starts after
  return result;
}

Because the input is already sorted, one pass is enough: O(n) instead of the O(n log n) of “append and call merge”. Using the existing order instead of sorting again is exactly the kind of improvement interviewers hope you’ll notice.

Comparators that overflow

Predict the output

What does this print?

let intervals = [[2_000_000_000, 2_000_000_001], [-2_000_000_000, 0]]
let sorted = intervals.sorted { $0[0] < $1[0] }
print(sorted[0][0])

val intervals = arrayOf(intArrayOf(2_000_000_000, 2_000_000_001), intArrayOf(-2_000_000_000, 0))
val sorted = intervals.sortedWith { a, b -> a[0] - b[0] }
println(sorted[0][0])

int[][] intervals = { { 2_000_000_000, 2_000_000_001 }, { -2_000_000_000, 0 } };
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
System.out.println(intervals[0][0]);

const intervals = [[2_000_000_000, 2_000_000_001], [-2_000_000_000, 0]];
const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
console.log(sorted[0][0]);

Timestamps in milliseconds or large IDs hit this in production; LeetCode-style constraints (-10⁹ ≤ x ≤ 10⁹) are chosen to trigger it too. Comparing with compare/compareTo is a habit worth showing.

Variants worth naming

Coverage questions (“is [a, b] fully covered?”, “total covered length”) are merge plus a sum.
Open intervals or touching rules change <= to <; ask before coding.
Many queries on a static set: merge once, then binary search the merged starts for each query, O(log n) per query.
Streaming inserts with queries (a dynamic calendar): an ordered map keyed by start (Java TreeMap, see the last part), or an interval tree.

Overlap: a.start <= b.end && b.start <= a.end (< for half-open). Clarify the convention.
Merge: sort by start, compare with the last merged, extend with max of ends (nested intervals). O(n log n).
Insert into a sorted, disjoint list: three phases (before, overlapping, after) in O(n), no re-sort.
Comparators: a[0] - b[0] overflows Int/int on the JVM; use compareBy / Integer.compare. Swift < is safe; TS subtraction is exact below 2⁵³.

Check this part

After sorting by start, which interval must the current one be compared with?
Sorted by start, an interval can only overlap the latest merged one.
Merging [1, 10] with [2, 3] gives…
The end is the larger of the two ends; [2, 3] lies inside [1, 10].
A Java teammate sorts intervals with (a, b) -> a[0] - b[0] on millisecond timestamps. What can go wrong?sortedWith { a, b -> a[0] - b[0] } on values up to ±2·10⁹. What can go wrong?(a, b) -> a[0] - b[0] on values up to ±2·10⁹. What can go wrong?A Java teammate sorts intervals with (a, b) -> a[0] - b[0] on values up to ±2·10⁹. What can go wrong?
Use Integer.compare / compareBy; TypeScript numbers don't overflow at that size.
Insert one interval into a sorted, non-overlapping list. Best approach?
The existing order makes sorting unnecessary; building the result is O(n) anyway.

Two intervals overlap when each starts before the other ends. Sort by start, and every interval only needs comparing with the last merged one: extend its end to the larger of the two ends, or start a new one.

Part Not started

How many rooms? The sweep line

Meeting Rooms II. Given meetings as [start, end), return the minimum number of rooms so every meeting has one. [[0, 30], [5, 10], [15, 20]] → 2. [[7, 10], [2, 4]] → 1.

Imagine walking along the timeline, watching meetings start and end. Each time a meeting starts, it needs a room; each time one ends, a room frees up. The most rooms you ever need at once is the answer.

You don’t need to know which meeting ends, only when the earliest one does. So sort all the start times, and separately all the end times, and walk through the starts. If the earliest end not yet passed comes at or before this start, a room has freed up and you reuse it. Otherwise you need a new room.

The answer is the maximum overlap depth. A sweep line over sorted event times computes it in O(n log n): starts and ends sorted independently (the identity of which meeting ends is irrelevant to the count), with the tie rule encoded in the comparison. For half-open intervals, an end at time t frees a room for a start at time t, so ends sort before starts at equal times.

Sweep through starts, reusing rooms that freed up

func minMeetingRooms(_ meetings: [[Int]]) -> Int {
    let starts = meetings.map { $0[0] }.sorted()
    let ends = meetings.map { $0[1] }.sorted()
    var rooms = 0, endIndex = 0
    for start in starts {
        if start < ends[endIndex] {
            rooms += 1                 // nothing has ended yet: open a new room
        } else {
            endIndex += 1              // a meeting ended: reuse its room
        }
    }
    return rooms
}

fun minMeetingRooms(meetings: Array<IntArray>): Int {
    val starts = meetings.map { it[0] }.sorted()
    val ends = meetings.map { it[1] }.sorted()
    var rooms = 0; var endIndex = 0
    for (start in starts) {
        if (start < ends[endIndex]) {
            rooms++                    // nothing has ended yet: open a new room
        } else {
            endIndex++                 // a meeting ended: reuse its room
        }
    }
    return rooms
}

int minMeetingRooms(int[][] meetings) {
    int[] starts = Arrays.stream(meetings).mapToInt(m -> m[0]).sorted().toArray();
    int[] ends = Arrays.stream(meetings).mapToInt(m -> m[1]).sorted().toArray();
    int rooms = 0, endIndex = 0;
    for (int start : starts) {
        if (start < ends[endIndex]) {
            rooms++;                   // nothing has ended yet: open a new room
        } else {
            endIndex++;                // a meeting ended: reuse its room
        }
    }
    return rooms;
}

function minMeetingRooms(meetings: number[][]): number {
  const starts = meetings.map((m) => m[0]).sort((a, b) => a - b);
  const ends = meetings.map((m) => m[1]).sort((a, b) => a - b);
  let rooms = 0, endIndex = 0;
  for (const start of starts) {
    if (start < ends[endIndex]) {
      rooms++;                         // nothing has ended yet: open a new room
    } else {
      endIndex++;                      // a meeting ended: reuse its room
    }
  }
  return rooms;
}

rooms never goes down: a freed room is reused by the next meeting instead of being given back, so the count is the number of rooms ever opened. Each start either opens a room or reuses one. Two sorts and one pass: O(n log n) time, O(n) space.

The comparison is <: a meeting that starts at 10 can use the room of one that ends at 10. If the rules said they collide, it would be <=.

Predict the output

How many rooms do these meetings need? [[1, 5], [2, 6], [3, 7], [6, 8]]

Practice: the events view

The same answer, drawn as events on a timeline, is the picture to keep in mind:

Turn each meeting into two events: (start, +1) and (end, −1).
Sort the events by time. At equal times, put −1 first (a meeting ending at 10 frees its room for one starting at 10).
Walk through them, adding up the +1s and −1s. The running total is the number of meetings happening right then.
The largest running total is the number of rooms.

For [[0, 30], [5, 10], [15, 20]]: events 0 (+1), 5 (+1), 10 (−1), 15 (+1), 20 (−1), 30 (−1). Totals: 1, 2, 1, 2, 1, 0. The peak is 2.

Ties decide correctness

Spot the bugBack-to-back meetings need an extra room

Tap the line with the bug.

func minMeetingRooms(_ meetings: [[Int]]) -> Int {
    let starts = meetings.map { $0[0] }.sorted()
    let ends = meetings.map { $0[1] }.sorted()
    var rooms = 0, endIndex = 0
    for start in starts {
        if start <= ends[endIndex] { rooms += 1 } else { endIndex += 1 }
    }
    return rooms
}

fun minMeetingRooms(meetings: Array<IntArray>): Int {
    val starts = meetings.map { it[0] }.sorted()
    val ends = meetings.map { it[1] }.sorted()
    var rooms = 0; var endIndex = 0
    for (start in starts) {
        if (start <= ends[endIndex]) rooms++ else endIndex++
    }
    return rooms
}

int minMeetingRooms(int[][] meetings) {
    int[] starts = Arrays.stream(meetings).mapToInt(m -> m[0]).sorted().toArray();
    int[] ends = Arrays.stream(meetings).mapToInt(m -> m[1]).sorted().toArray();
    int rooms = 0, endIndex = 0;
    for (int start : starts) {
        if (start <= ends[endIndex]) rooms++; else endIndex++;
    }
    return rooms;
}

function minMeetingRooms(meetings: number[][]): number {
  const starts = meetings.map((m) => m[0]).sort((a, b) => a - b);
  const ends = meetings.map((m) => m[1]).sort((a, b) => a - b);
  let rooms = 0, endIndex = 0;
  for (const start of starts) {
    if (start <= ends[endIndex]) rooms++; else endIndex++;
  }
  return rooms;
}

The heap version

Keeping a min-heap of end times answers the same question and generalizes better: sort meetings by start; for each, if the heap’s smallest end is <= its start, pop it (that room frees up); push the meeting’s end. The heap size at the end (or its maximum) is the room count. It’s still O(n log n), but the heap tells you which room each meeting gets, which the two-array version can’t. That matters for follow-ups like “assign room numbers” or “rooms have different capacities”. See Heaps.

Rooms = maximum overlap depth. Sweep: sort starts and ends separately; start < ends[j] → new room, else j++. O(n log n).
Events view: (t, +1), (t, −1), sort by time with ends first at ties for half-open intervals; the running sum’s maximum is the answer.
<= vs < is the tie rule: half-open back-to-back meetings share a room. Clarify it.
Min-heap of end times when you also need the assignment (which room, capacities).

Sweep with a heap (assignment-friendly)

// Swift has no built-in heap: use Heap from swift-collections, or the two-array sweep.

fun minMeetingRooms(meetings: Array<IntArray>): Int {
    val ends = java.util.PriorityQueue<Int>()
    for (m in meetings.sortedBy { it[0] }) {
        if (ends.isNotEmpty() && ends.peek() <= m[0]) ends.poll()
        ends.add(m[1])
    }
    return ends.size
}

int minMeetingRooms(int[][] meetings) {
    int[][] sorted = meetings.clone();
    Arrays.sort(sorted, Comparator.comparingInt(m -> m[0]));
    PriorityQueue<Integer> ends = new PriorityQueue<>();
    for (int[] m : sorted) {
        if (!ends.isEmpty() && ends.peek() <= m[0]) ends.poll();
        ends.add(m[1]);
    }
    return ends.size();
}

// No built-in heap in TypeScript: use the two-array sweep, or a small binary-heap class.

Check this part

What does the minimum number of meeting rooms equal?
At the busiest moment every running meeting needs its own room.
Why can starts and ends be sorted separately?
A freed room is a freed room, whichever meeting held it.
Half-open meetings [9, 10) and [10, 11). Which comparison counts a new room correctly?
A start equal to an end can reuse that room; <= would double-count back-to-back meetings.
When is the min-heap of end times better than two sorted arrays?
Both are O(n log n); the heap keeps track of individual rooms.

The number of rooms you need is the largest number of meetings happening at the same moment. Sort the starts and the ends separately and sweep through time: a start takes a room unless a meeting has already ended.

Part Not started

Keeping intervals apart

Non-overlapping Intervals. Return the minimum number of intervals to remove so the rest don’t overlap (touching ends are fine). [[1, 2], [2, 3], [3, 4], [1, 3]] → 1. [[1, 2], [1, 2], [1, 2]] → 2.

Removing the fewest is the same as keeping the most, and keeping the most is the classic greedy: always keep the interval that ends earliest, because it leaves the most room for everything after it.

Sort by end, keep what fits

func eraseOverlapIntervals(_ intervals: [[Int]]) -> Int {
    let sorted = intervals.sorted { $0[1] < $1[1] }
    var kept = 0
    var lastEnd = Int.min
    for interval in sorted where interval[0] >= lastEnd {
        kept += 1                       // starts after the last kept one ends: keep it
        lastEnd = interval[1]
    }
    return intervals.count - kept
}

fun eraseOverlapIntervals(intervals: Array<IntArray>): Int {
    var kept = 0
    var lastEnd = Int.MIN_VALUE
    for (interval in intervals.sortedBy { it[1] }) {
        if (interval[0] >= lastEnd) {
            kept++                      // starts after the last kept one ends: keep it
            lastEnd = interval[1]
        }
    }
    return intervals.size - kept
}

int eraseOverlapIntervals(int[][] intervals) {
    int[][] sorted = intervals.clone();
    Arrays.sort(sorted, Comparator.comparingInt(a -> a[1]));
    int kept = 0;
    long lastEnd = Long.MIN_VALUE;
    for (int[] interval : sorted) {
        if (interval[0] >= lastEnd) {
            kept++;                     // starts after the last kept one ends: keep it
            lastEnd = interval[1];
        }
    }
    return intervals.length - kept;
}

function eraseOverlapIntervals(intervals: number[][]): number {
  const sorted = [...intervals].sort((a, b) => a[1] - b[1]);
  let kept = 0;
  let lastEnd = -Infinity;
  for (const [start, end] of sorted) {
    if (start >= lastEnd) {
      kept++;                           // starts after the last kept one ends: keep it
      lastEnd = end;
    }
  }
  return intervals.length - kept;
}

Notice the sort key changed: merging sorts by start, choosing sorts by end. When you’re combining intervals, you need them in the order they begin. When you’re choosing which to keep, the one that frees the timeline soonest is the safe choice. The Greedy algorithms lesson shows why “shortest first” or “earliest start” give wrong answers here.

This is interval scheduling (activity selection), optimal by “greedy stays ahead”: the k-th interval greedy keeps ends no later than the k-th of any valid selection. The minimum number of points that stab every interval (“minimum arrows to burst balloons”) is the same algorithm with a closed-interval comparison, and the minimum removal count is n − kept.

Exercisemedium

Interval List Intersections

Two lists of closed intervals, each sorted and without overlaps inside the list. Return their intersection: every range that’s in both.

a = [[0, 2], [5, 10], [13, 23], [24, 25]]
b = [[1, 5], [8, 12], [15, 24], [25, 26]]
→ [[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]

›

Use one pointer per list. Two intervals intersect in [max of starts, min of ends], if that range isn’t empty.

›

After comparing a[i] and b[j], advance the one that ends first: it can’t intersect anything further in the other list.

SolutionTry it yourself firstTime O(m + n)Space O(1) besides the output

func intervalIntersection(_ a: [[Int]], _ b: [[Int]]) -> [[Int]] {
    var result: [[Int]] = []
    var i = 0, j = 0
    while i < a.count && j < b.count {
        let low = max(a[i][0], b[j][0])
        let high = min(a[i][1], b[j][1])
        if low <= high { result.append([low, high]) }
        if a[i][1] < b[j][1] { i += 1 } else { j += 1 }   // the one that ends first is done
    }
    return result
}

fun intervalIntersection(a: Array<IntArray>, b: Array<IntArray>): Array<IntArray> {
    val result = mutableListOf<IntArray>()
    var i = 0; var j = 0
    while (i < a.size && j < b.size) {
        val low = maxOf(a[i][0], b[j][0])
        val high = minOf(a[i][1], b[j][1])
        if (low <= high) result.add(intArrayOf(low, high))
        if (a[i][1] < b[j][1]) i++ else j++               // the one that ends first is done
    }
    return result.toTypedArray()
}

int[][] intervalIntersection(int[][] a, int[][] b) {
    List<int[]> result = new ArrayList<>();
    int i = 0, j = 0;
    while (i < a.length && j < b.length) {
        int low = Math.max(a[i][0], b[j][0]);
        int high = Math.min(a[i][1], b[j][1]);
        if (low <= high) result.add(new int[] { low, high });
        if (a[i][1] < b[j][1]) i++; else j++;              // the one that ends first is done
    }
    return result.toArray(new int[0][]);
}

function intervalIntersection(a: number[][], b: number[][]): number[][] {
  const result: number[][] = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    const low = Math.max(a[i][0], b[j][0]);
    const high = Math.min(a[i][1], b[j][1]);
    if (low <= high) result.push([low, high]);
    if (a[i][1] < b[j][1]) i++; else j++;              // the one that ends first is done
  }
  return result;
}

It’s the two pointers idea on intervals: each step finishes one interval for good, so the loop runs at most m + n times, with no sorting because both lists are already sorted.

Exercisemedium

A booking calendar

Design a MyCalendar class with book(start, end) -> Bool for half-open ranges [start, end). It books the range and returns true if it doesn’t overlap any existing booking; otherwise it returns false and books nothing. Expect up to 10⁵ calls. Then discuss: what changes when this backs a real room-booking service?

›

Keep bookings sorted by start, non-overlapping. A new range only needs checking against two neighbors: the booking that starts at or before it, and the one that starts after it.

›

Java and Kotlin have TreeMap with floorEntry and ceilingEntry, O(log n). Swift and TypeScript don’t have a sorted map: binary search a sorted array for the position, then insert (O(n) shift, but contiguous and fast in practice).

SolutionTry it yourself firstTime O(log n) per book with a TreeMap; O(n) with a sorted arraySpace O(n)

struct MyCalendar {
    private var booked: [(start: Int, end: Int)] = []   // sorted by start, never overlapping

    mutating func book(_ start: Int, _ end: Int) -> Bool {
        var low = 0, high = booked.count                 // first booking with start >= start
        while low < high {
            let mid = (low + high) / 2
            if booked[mid].start < start { low = mid + 1 } else { high = mid }
        }
        if low > 0 && booked[low - 1].end > start { return false }          // previous runs into it
        if low < booked.count && booked[low].start < end { return false }   // next starts too early
        booked.insert((start, end), at: low)
        return true
    }
}

class MyCalendar {
    private val booked = java.util.TreeMap<Int, Int>()   // start → end

    fun book(start: Int, end: Int): Boolean {
        val previous = booked.floorEntry(start)
        val next = booked.ceilingEntry(start)
        if (previous != null && previous.value > start) return false   // previous runs into it
        if (next != null && next.key < end) return false              // next starts too early
        booked[start] = end
        return true
    }
}

class MyCalendar {
    private final TreeMap<Integer, Integer> booked = new TreeMap<>();   // start → end

    public boolean book(int start, int end) {
        Map.Entry<Integer, Integer> previous = booked.floorEntry(start);
        Map.Entry<Integer, Integer> next = booked.ceilingEntry(start);
        if (previous != null && previous.getValue() > start) return false;   // previous runs into it
        if (next != null && next.getKey() < end) return false;              // next starts too early
        booked.put(start, end);
        return true;
    }
}

class MyCalendar {
  private readonly booked: [number, number][] = [];    // sorted by start, never overlapping

  book(start: number, end: number): boolean {
    let low = 0, high = this.booked.length;            // first booking with start >= start
    while (low < high) {
      const mid = (low + high) >> 1;
      if (this.booked[mid][0] < start) low = mid + 1; else high = mid;
    }
    if (low > 0 && this.booked[low - 1][1] > start) return false;                     // previous runs into it
    if (low < this.booked.length && this.booked[low][0] < end) return false;          // next starts too early
    this.booked.splice(low, 0, [start, end]);
    return true;
  }
}

Why two neighbors suffice: the stored bookings never overlap and are sorted, so only the closest one on each side can intersect the new range.
Ordered map vs sorted array: TreeMap is O(log n) for both search and insert; the array is O(log n) to search and O(n) to insert, but with 10⁵ small entries the shift is a fast memory move. Say which you’d pick and why.
In a real service the in-memory structure is the easy part. Two concurrent requests can both see “free” and both insert. Enforce non-overlap where the data lives: a database exclusion constraint (PostgreSQL EXCLUDE USING gist on a time range per room), or a transaction that locks the room’s row, with the in-memory check only as a fast pre-filter. Also decide on the time model: UTC instants, half-open ranges, and time zones only for display.

Goal	Sort by	One-pass rule
Merge / coverage	start	extend `last.end = max(...)` or append
Max non-overlapping / min removals / min arrows	end	keep if `start >= lastEnd` (closed: `>`)
Min rooms / max overlap	starts and ends separately, or events	`start < ends[j]` → room++, else j++
Intersect two sorted lists	(already sorted)	`[max starts, min ends]`, advance the earlier end
Dynamic bookings	ordered map by start	check floor and ceiling neighbors

Correctness lives in two places: the sort key and the tie convention. In production, enforce non-overlap in the database (exclusion constraint or locking), not only in memory.

Check this part

To keep the most non-overlapping intervals, sort by…
The interval that ends first leaves the most room for the rest.
Intersecting two sorted lists with two pointers: which pointer moves after a comparison?
That interval can't overlap anything later in the other list.
Minimum removals so the rest don't overlap equals…
Removing the fewest is keeping the most, which is interval scheduling.
A booking service checks a sorted in-memory map before inserting. What can still double-book a room?
Enforce non-overlap in the database with an exclusion constraint or a lock.

To keep the most non-overlapping intervals (or remove the fewest), sort by end and keep each interval that starts after the last kept one ends. Two sorted lists are intersected with two pointers that advance whichever interval ends first.

Key takeaways

Two intervals overlap when each starts before the other ends.
Merging sorts by start and extends the last interval with the larger end.
The number of rooms is the most meetings at the same moment: sweep through sorted starts and ends.
Keeping the most non-overlapping intervals sorts by end and keeps whatever starts after the last kept one ends.

Pick the sort key by goal: start for merging and coverage, end for selection, separate starts and ends for depth.
Clarify closed vs half-open; it decides every < vs <= and back-to-back behavior.
Avoid subtraction comparators on the JVM; use compareBy or Integer.compare.
Dynamic bookings need an ordered map (or sorted array with binary search) and, in production, a database-level guarantee against concurrent double-booking.