ReslandDSA Study Center

Intervals

Sort ranges by their start so overlaps sit side by side, then merge, insert or count them in a single pass.

IntermediateRead first: Sorting

How It Works

An interval is a pair [start, end]: a meeting, a booking, a range of numbers. Interval problems ask you to merge the ones that overlap, slot a new one in, or count how many are active at once. Comparing every pair with every other works, but it costs O(n²).

Sort by start and the problem becomes local. Walk the intervals in order while you build one merged block at a time. The next interval can only overlap the block you're building: every finished block ended before this block began, and the next interval starts no earlier than this block did.

         0    5    10   15
         |    |    |    |
[1,3]     ===
[2,6]      =====
[8,10]           ===
[15,18]                 ====

merged    ====== ===    ====
Sorted by start, each interval either overlaps the block being built or starts a new one.

Merge Intervals, Step by Step

Step 1 of 7

intervals

merged

  • Interval being placed
  • Block being built
  • Finished block
  • Already placed

The 4 intervals arrive in no particular order. Checking every pair for overlap would cost O(n²), so sort them by start first.

All 7 steps as text
  1. The 4 intervals arrive in no particular order. Checking every pair for overlap would cost O(n²), so sort them by start first.
  2. Sorted by start: [1, 3], [2, 6], [8, 10], [15, 18]. Now an interval can only overlap the block built just before it.
  3. merged is empty, so [1, 3] starts the first block.
  4. [2, 6] starts at 2, no later than the block's end 3, so they overlap. Extend the block to max(3, 6) = 6.
  5. 8 is after the block's end 6, and every later interval starts at 8 or later. So [1, 6] is finished, and [8, 10] starts a new block.
  6. 15 is after the block's end 10, and every later interval starts at 15 or later. So [8, 10] is finished, and [15, 18] starts a new block.
  7. That's every interval, so the last block is finished too. The answer is [[1, 6], [8, 10], [15, 18]], after one pass over the sorted list.

Two intervals [a, b] and [c, d] overlap when a <= d and c <= b. Once they're sorted so that a <= c, the first half always holds, which leaves one check: does the next interval start before the current block ends? Whether touching counts depends on the problem. Merge Intervals treats [1, 4] and [4, 5] as overlapping, so it uses <=. Two meetings at those times don't clash, because the first ends as the second starts.

The common shapes:

  • Merge. Sort by start and keep extending the current block while the next interval overlaps it. That's the template below.
  • Insert. When the list is already sorted and overlap-free, skip the sort: copy what comes before the new interval, absorb what overlaps it, copy what comes after. That's O(n).
  • Count overlaps. Sort the start times and end times separately and sweep through them in time order. The most intervals active at once answers meeting rooms, car pooling and similar questions.
  • Keep the most. To keep as many non-overlapping intervals as possible, sort by end and keep taking the next one that starts after the last one you kept ends. Finishing as early as possible leaves the most room for the rest, which is a greedy choice.

When to Reach for It

  • The input is a list of [start, end] pairs: meetings, bookings, time slots or number ranges.
  • The question asks you to merge, insert or remove overlapping ranges.
  • You need the most things happening at the same moment: rooms, platforms, servers, passengers in a car.
  • You need the gaps between ranges, such as the free time in a calendar.

Complexity

OperationTimeSpace
Sort by startO(n log n)O(1) to O(n), depending on the sort
Merge after sortingO(n)O(n) for the output
Insert into a sorted, overlap-free listO(n)O(n) for the output
Most intervals active at onceO(n log n)O(n)

The Template

Merge Intervals

Sort a copy of the intervals by start, then walk it while building the result. If the next interval starts at or before the end of the last merged block, the two overlap, so extend that block. Otherwise there's a gap, and the interval starts a new block. After the sort, each interval is handled once, so the sort dominates the running time.

Time O(n log n)Space O(n)

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    """Merges overlapping intervals and returns them sorted by start. Intervals
    that only touch, like [1, 4] and [4, 5], count as overlapping."""
    merged: list[list[int]] = []
    # Sort by start so intervals that overlap end up next to each other.
    for start, end in sorted(intervals, key=lambda interval: interval[0]):
        if merged and start <= merged[-1][1]:
            # Overlaps the block being built. Keep the larger end, because this
            # interval may sit entirely inside the block.
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])  # A gap: start a new block.
    return merged


if __name__ == "__main__":
    print(merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]))  # [[1, 6], [8, 10], [15, 18]]
    print(merge_intervals([[1, 4], [4, 5]]))  # [[1, 5]]
    print(merge_intervals([[4, 7], [1, 10], [2, 3]]))  # [[1, 10]]
// Merges overlapping intervals and returns them sorted by start. Intervals
// that only touch, like [1, 4] and [4, 5], count as overlapping.
export function mergeIntervals(intervals: number[][]): number[][] {
  // Sort by start so intervals that overlap end up next to each other.
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const merged: number[][] = [];
  for (const [start, end] of sorted) {
    const last = merged.at(-1);
    if (last !== undefined && start <= last[1]) {
      // Overlaps the block being built. Keep the larger end, because this
      // interval may sit entirely inside the block.
      last[1] = Math.max(last[1], end);
    } else {
      merged.push([start, end]); // A gap: start a new block.
    }
  }
  return merged;
}

console.log(JSON.stringify(mergeIntervals([[1, 3], [2, 6], [8, 10], [15, 18]]))); // [[1,6],[8,10],[15,18]]
console.log(JSON.stringify(mergeIntervals([[1, 4], [4, 5]]))); // [[1,5]]
console.log(JSON.stringify(mergeIntervals([[4, 7], [1, 10], [2, 3]]))); // [[1,10]]
package main

import (
	"cmp"
	"fmt"
	"slices"
)

// mergeIntervals merges overlapping intervals and returns them sorted by
// start. Intervals that only touch, like [1, 4] and [4, 5], count as
// overlapping.
func mergeIntervals(intervals [][]int) [][]int {
	// Sort by start so intervals that overlap end up next to each other.
	sorted := slices.Clone(intervals)
	slices.SortFunc(sorted, func(a, b []int) int { return cmp.Compare(a[0], b[0]) })
	merged := [][]int{}
	for _, interval := range sorted {
		start, end := interval[0], interval[1]
		if n := len(merged); n > 0 && start <= merged[n-1][1] {
			// Overlaps the block being built. Keep the larger end, because this
			// interval may sit entirely inside the block.
			merged[n-1][1] = max(merged[n-1][1], end)
		} else {
			merged = append(merged, []int{start, end}) // A gap: start a new block.
		}
	}
	return merged
}

func main() {
	fmt.Println(mergeIntervals([][]int{{1, 3}, {2, 6}, {8, 10}, {15, 18}})) // [[1 6] [8 10] [15 18]]
	fmt.Println(mergeIntervals([][]int{{1, 4}, {4, 5}}))                    // [[1 5]]
	fmt.Println(mergeIntervals([][]int{{4, 7}, {1, 10}, {2, 3}}))           // [[1 10]]
}
using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    // Merges overlapping intervals and returns them sorted by start. Intervals
    // that only touch, like [1, 4] and [4, 5], count as overlapping.
    public static List<int[]> MergeIntervals(int[][] intervals)
    {
        // Sort by start so intervals that overlap end up next to each other.
        var sorted = intervals.OrderBy(interval => interval[0]).ToArray();
        var merged = new List<int[]>();
        foreach (var interval in sorted)
        {
            int start = interval[0], end = interval[1];
            if (merged.Count > 0 && start <= merged[^1][1])
            {
                // Overlaps the block being built. Keep the larger end, because this
                // interval may sit entirely inside the block.
                merged[^1][1] = Math.Max(merged[^1][1], end);
            }
            else
            {
                merged.Add(new[] { start, end }); // A gap: start a new block.
            }
        }
        return merged;
    }

    public static void Main()
    {
        Console.WriteLine(Format(MergeIntervals([[1, 3], [2, 6], [8, 10], [15, 18]]))); // [[1, 6], [8, 10], [15, 18]]
        Console.WriteLine(Format(MergeIntervals([[1, 4], [4, 5]]))); // [[1, 5]]
        Console.WriteLine(Format(MergeIntervals([[4, 7], [1, 10], [2, 3]]))); // [[1, 10]]
    }

    static string Format(List<int[]> intervals) =>
        "[" + string.Join(", ", intervals.Select(i => "[" + string.Join(", ", i) + "]")) + "]";
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Solution {
    // Merges overlapping intervals and returns them sorted by start. Intervals
    // that only touch, like [1, 4] and [4, 5], count as overlapping.
    static int[][] mergeIntervals(int[][] intervals) {
        // Sort by start so intervals that overlap end up next to each other.
        int[][] sorted = intervals.clone();
        Arrays.sort(sorted, Comparator.comparingInt(interval -> interval[0]));
        List<int[]> merged = new ArrayList<>();
        for (int[] interval : sorted) {
            int start = interval[0], end = interval[1];
            if (!merged.isEmpty() && start <= merged.get(merged.size() - 1)[1]) {
                // Overlaps the block being built. Keep the larger end, because this
                // interval may sit entirely inside the block.
                int[] last = merged.get(merged.size() - 1);
                last[1] = Math.max(last[1], end);
            } else {
                merged.add(new int[] {start, end}); // A gap: start a new block.
            }
        }
        return merged.toArray(new int[0][]);
    }

    public static void main(String[] args) {
        System.out.println(Arrays.deepToString(mergeIntervals(new int[][] {{1, 3}, {2, 6}, {8, 10}, {15, 18}}))); // [[1, 6], [8, 10], [15, 18]]
        System.out.println(Arrays.deepToString(mergeIntervals(new int[][] {{1, 4}, {4, 5}}))); // [[1, 5]]
        System.out.println(Arrays.deepToString(mergeIntervals(new int[][] {{4, 7}, {1, 10}, {2, 3}}))); // [[1, 10]]
    }
}

Worked Problems

Each solution stays folded until you open it, so you can try the problem first. Every one is a complete program in Python, TypeScript, Go, C# and Java, run and checked against its expected output.

Insert Interval

MEDIUMLeetCode 57

Problem

You're given a list of intervals that don't overlap and are sorted by start, plus one new interval. Add the new interval, merging it with anything it overlaps, so the result is still sorted and overlap-free.

Example: inserting [4, 8] into [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]] returns [[1, 2], [3, 10], [12, 16]]. The new interval swallows [3, 5], [6, 7] and [8, 10].

Show Solution

Approach

You could append it and run Merge Intervals, but that sorts a list that's already sorted. Because the list is in order, it splits into three runs, and one pass handles each:

  1. Intervals that end before the new one starts can't touch it. Copy them over unchanged.
  2. Intervals that start at or before the new one's end overlap it. Absorb each one by widening the new interval to the smaller start and the larger end.
  3. Add the widened interval, then copy everything that's left. All of it starts after the widened interval ends.

The checks match the merge template, where touching counts as overlapping. That's why the first run uses a strict < and the second uses <=. Every interval is visited once, so the whole thing is O(n).

Time O(n)Space O(n) for the output

def insert_interval(intervals: list[list[int]], new_interval: list[int]) -> list[list[int]]:
    """Inserts `new_interval` into `intervals` (non-overlapping and sorted by
    start), merging it with every interval it overlaps."""
    result: list[list[int]] = []
    start, end = new_interval
    i = 0
    # 1. Intervals that end before the new one starts come first, unchanged.
    while i < len(intervals) and intervals[i][1] < start:
        result.append(intervals[i])
        i += 1
    # 2. Intervals that start at or before the new one's end overlap it: absorb them.
    while i < len(intervals) and intervals[i][0] <= end:
        start = min(start, intervals[i][0])
        end = max(end, intervals[i][1])
        i += 1
    result.append([start, end])
    # 3. Everything left starts after the merged interval ends.
    while i < len(intervals):
        result.append(intervals[i])
        i += 1
    return result


if __name__ == "__main__":
    print(insert_interval([[1, 3], [6, 9]], [2, 5]))  # [[1, 5], [6, 9]]
    print(insert_interval([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]))  # [[1, 2], [3, 10], [12, 16]]
    print(insert_interval([], [5, 7]))  # [[5, 7]]
// Inserts newInterval into intervals (non-overlapping and sorted by start),
// merging it with every interval it overlaps.
export function insertInterval(intervals: number[][], newInterval: number[]): number[][] {
  const result: number[][] = [];
  let [start, end] = newInterval;
  let i = 0;
  // 1. Intervals that end before the new one starts come first, unchanged.
  while (i < intervals.length && intervals[i][1] < start) {
    result.push(intervals[i]);
    i++;
  }
  // 2. Intervals that start at or before the new one's end overlap it: absorb them.
  while (i < intervals.length && intervals[i][0] <= end) {
    start = Math.min(start, intervals[i][0]);
    end = Math.max(end, intervals[i][1]);
    i++;
  }
  result.push([start, end]);
  // 3. Everything left starts after the merged interval ends.
  while (i < intervals.length) {
    result.push(intervals[i]);
    i++;
  }
  return result;
}

console.log(JSON.stringify(insertInterval([[1, 3], [6, 9]], [2, 5]))); // [[1,5],[6,9]]
console.log(JSON.stringify(insertInterval([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]))); // [[1,2],[3,10],[12,16]]
console.log(JSON.stringify(insertInterval([], [5, 7]))); // [[5,7]]
package main

import "fmt"

// insertInterval inserts newInterval into intervals (non-overlapping and
// sorted by start), merging it with every interval it overlaps.
func insertInterval(intervals [][]int, newInterval []int) [][]int {
	result := [][]int{}
	start, end := newInterval[0], newInterval[1]
	i := 0
	// 1. Intervals that end before the new one starts come first, unchanged.
	for i < len(intervals) && intervals[i][1] < start {
		result = append(result, intervals[i])
		i++
	}
	// 2. Intervals that start at or before the new one's end overlap it: absorb them.
	for i < len(intervals) && intervals[i][0] <= end {
		start = min(start, intervals[i][0])
		end = max(end, intervals[i][1])
		i++
	}
	result = append(result, []int{start, end})
	// 3. Everything left starts after the merged interval ends.
	for i < len(intervals) {
		result = append(result, intervals[i])
		i++
	}
	return result
}

func main() {
	fmt.Println(insertInterval([][]int{{1, 3}, {6, 9}}, []int{2, 5}))                            // [[1 5] [6 9]]
	fmt.Println(insertInterval([][]int{{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}}, []int{4, 8})) // [[1 2] [3 10] [12 16]]
	fmt.Println(insertInterval([][]int{}, []int{5, 7}))                                          // [[5 7]]
}
using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    // Inserts newInterval into intervals (non-overlapping and sorted by start),
    // merging it with every interval it overlaps.
    public static List<int[]> InsertInterval(int[][] intervals, int[] newInterval)
    {
        var result = new List<int[]>();
        int start = newInterval[0], end = newInterval[1];
        int i = 0;
        // 1. Intervals that end before the new one starts come first, unchanged.
        while (i < intervals.Length && intervals[i][1] < start)
        {
            result.Add(intervals[i]);
            i++;
        }
        // 2. Intervals that start at or before the new one's end overlap it: absorb them.
        while (i < intervals.Length && intervals[i][0] <= end)
        {
            start = Math.Min(start, intervals[i][0]);
            end = Math.Max(end, intervals[i][1]);
            i++;
        }
        result.Add(new[] { start, end });
        // 3. Everything left starts after the merged interval ends.
        while (i < intervals.Length)
        {
            result.Add(intervals[i]);
            i++;
        }
        return result;
    }

    public static void Main()
    {
        Console.WriteLine(Format(InsertInterval([[1, 3], [6, 9]], [2, 5]))); // [[1, 5], [6, 9]]
        Console.WriteLine(Format(InsertInterval([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]))); // [[1, 2], [3, 10], [12, 16]]
        Console.WriteLine(Format(InsertInterval([], [5, 7]))); // [[5, 7]]
    }

    static string Format(List<int[]> intervals) =>
        "[" + string.Join(", ", intervals.Select(i => "[" + string.Join(", ", i) + "]")) + "]";
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    // Inserts newInterval into intervals (non-overlapping and sorted by start),
    // merging it with every interval it overlaps.
    static int[][] insertInterval(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int start = newInterval[0], end = newInterval[1];
        int i = 0;
        // 1. Intervals that end before the new one starts come first, unchanged.
        while (i < intervals.length && intervals[i][1] < start) {
            result.add(intervals[i]);
            i++;
        }
        // 2. Intervals that start at or before the new one's end overlap it: absorb them.
        while (i < intervals.length && intervals[i][0] <= end) {
            start = Math.min(start, intervals[i][0]);
            end = Math.max(end, intervals[i][1]);
            i++;
        }
        result.add(new int[] {start, end});
        // 3. Everything left starts after the merged interval ends.
        while (i < intervals.length) {
            result.add(intervals[i]);
            i++;
        }
        return result.toArray(new int[0][]);
    }

    public static void main(String[] args) {
        System.out.println(Arrays.deepToString(insertInterval(new int[][] {{1, 3}, {6, 9}}, new int[] {2, 5}))); // [[1, 5], [6, 9]]
        System.out.println(Arrays.deepToString(insertInterval(new int[][] {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}}, new int[] {4, 8}))); // [[1, 2], [3, 10], [12, 16]]
        System.out.println(Arrays.deepToString(insertInterval(new int[][] {}, new int[] {5, 7}))); // [[5, 7]]
    }
}

Meeting Rooms II

MEDIUMLintCode 919

Problem

Each meeting is a pair [start, end] with start < end. Find the fewest conference rooms that can host all of them. A room is free the moment its meeting ends, so a meeting that ends at 10 and one that starts at 10 can share it.

Example: [[0, 30], [5, 10], [15, 20]] returns 2. The long meeting needs a room the whole time, and the other two take turns in a second one.

Show Solution

Approach

The answer is the largest number of meetings running at the same moment. You need at least that many rooms, and that many is enough, because a room that frees up can go to any meeting that starts later.

time     0    5    10   15   20   25   30
[0,30]   ==============================
[5,10]        =====
[15,20]                 =====
rooms    1    2    1    2    1         0
Rooms in use after each start or end. It never goes above two.

To find that peak, sort the start times and the end times separately, then walk the starts in order. Before each start, release every meeting that has ended by then, and then give the new meeting a room. The count of rooms in use rises and falls exactly as it does on the timeline, and its highest point is the answer. Splitting starts from ends is safe because you only ever count how many meetings are running, never which ones.

Time O(n log n)Space O(n)

def min_meeting_rooms(meetings: list[list[int]]) -> int:
    """Fewest rooms that can hold every meeting. Each meeting is [start, end]
    with start < end, and a room is free again the moment a meeting ends."""
    # Only the order of events matters, not which start goes with which end.
    starts = sorted(meeting[0] for meeting in meetings)
    ends = sorted(meeting[1] for meeting in meetings)
    rooms = 0  # Rooms in use right now.
    best = 0
    ended = 0  # Meetings that have finished so far.
    for start in starts:
        # Free the room of every meeting that's over. An end equal to this start
        # counts, so back-to-back meetings can share a room.
        while ends[ended] <= start:
            ended += 1
            rooms -= 1
        rooms += 1  # This meeting takes a room.
        best = max(best, rooms)
    return best


if __name__ == "__main__":
    print(min_meeting_rooms([[0, 30], [5, 10], [15, 20]]))  # 2
    print(min_meeting_rooms([[7, 10], [2, 4]]))  # 1
    print(min_meeting_rooms([[1, 5], [5, 10], [10, 15]]))  # 1
    print(min_meeting_rooms([[1, 10], [2, 7], [3, 19], [8, 12], [10, 20], [11, 30]]))  # 4
// Fewest rooms that can hold every meeting. Each meeting is [start, end]
// with start < end, and a room is free again the moment a meeting ends.
export function minMeetingRooms(meetings: number[][]): number {
  // Only the order of events matters, not which start goes with which end.
  const starts = meetings.map((meeting) => meeting[0]).sort((a, b) => a - b);
  const ends = meetings.map((meeting) => meeting[1]).sort((a, b) => a - b);
  let rooms = 0; // Rooms in use right now.
  let best = 0;
  let ended = 0; // Meetings that have finished so far.
  for (const start of starts) {
    // Free the room of every meeting that's over. An end equal to this start
    // counts, so back-to-back meetings can share a room.
    while (ends[ended] <= start) {
      ended++;
      rooms--;
    }
    rooms++; // This meeting takes a room.
    best = Math.max(best, rooms);
  }
  return best;
}

console.log(minMeetingRooms([[0, 30], [5, 10], [15, 20]])); // 2
console.log(minMeetingRooms([[7, 10], [2, 4]])); // 1
console.log(minMeetingRooms([[1, 5], [5, 10], [10, 15]])); // 1
console.log(minMeetingRooms([[1, 10], [2, 7], [3, 19], [8, 12], [10, 20], [11, 30]])); // 4
package main

import (
	"fmt"
	"slices"
)

// minMeetingRooms returns the fewest rooms that can hold every meeting. Each
// meeting is [start, end] with start < end, and a room is free again the
// moment a meeting ends.
func minMeetingRooms(meetings [][]int) int {
	// Only the order of events matters, not which start goes with which end.
	starts := make([]int, len(meetings))
	ends := make([]int, len(meetings))
	for i, meeting := range meetings {
		starts[i], ends[i] = meeting[0], meeting[1]
	}
	slices.Sort(starts)
	slices.Sort(ends)
	rooms := 0 // Rooms in use right now.
	best := 0
	ended := 0 // Meetings that have finished so far.
	for _, start := range starts {
		// Free the room of every meeting that's over. An end equal to this start
		// counts, so back-to-back meetings can share a room.
		for ends[ended] <= start {
			ended++
			rooms--
		}
		rooms++ // This meeting takes a room.
		best = max(best, rooms)
	}
	return best
}

func main() {
	fmt.Println(minMeetingRooms([][]int{{0, 30}, {5, 10}, {15, 20}}))                            // 2
	fmt.Println(minMeetingRooms([][]int{{7, 10}, {2, 4}}))                                       // 1
	fmt.Println(minMeetingRooms([][]int{{1, 5}, {5, 10}, {10, 15}}))                             // 1
	fmt.Println(minMeetingRooms([][]int{{1, 10}, {2, 7}, {3, 19}, {8, 12}, {10, 20}, {11, 30}})) // 4
}
using System;
using System.Linq;

public class Solution
{
    // Fewest rooms that can hold every meeting. Each meeting is [start, end]
    // with start < end, and a room is free again the moment a meeting ends.
    public static int MinMeetingRooms(int[][] meetings)
    {
        // Only the order of events matters, not which start goes with which end.
        int[] starts = meetings.Select(meeting => meeting[0]).Order().ToArray();
        int[] ends = meetings.Select(meeting => meeting[1]).Order().ToArray();
        int rooms = 0; // Rooms in use right now.
        int best = 0;
        int ended = 0; // Meetings that have finished so far.
        foreach (int start in starts)
        {
            // Free the room of every meeting that's over. An end equal to this start
            // counts, so back-to-back meetings can share a room.
            while (ends[ended] <= start)
            {
                ended++;
                rooms--;
            }
            rooms++; // This meeting takes a room.
            best = Math.Max(best, rooms);
        }
        return best;
    }

    public static void Main()
    {
        Console.WriteLine(MinMeetingRooms([[0, 30], [5, 10], [15, 20]])); // 2
        Console.WriteLine(MinMeetingRooms([[7, 10], [2, 4]])); // 1
        Console.WriteLine(MinMeetingRooms([[1, 5], [5, 10], [10, 15]])); // 1
        Console.WriteLine(MinMeetingRooms([[1, 10], [2, 7], [3, 19], [8, 12], [10, 20], [11, 30]])); // 4
    }
}
import java.util.Arrays;

public class Solution {
    // Fewest rooms that can hold every meeting. Each meeting is [start, end]
    // with start < end, and a room is free again the moment a meeting ends.
    static int minMeetingRooms(int[][] meetings) {
        // Only the order of events matters, not which start goes with which end.
        int[] starts = Arrays.stream(meetings).mapToInt(meeting -> meeting[0]).sorted().toArray();
        int[] ends = Arrays.stream(meetings).mapToInt(meeting -> meeting[1]).sorted().toArray();
        int rooms = 0; // Rooms in use right now.
        int best = 0;
        int ended = 0; // Meetings that have finished so far.
        for (int start : starts) {
            // Free the room of every meeting that's over. An end equal to this start
            // counts, so back-to-back meetings can share a room.
            while (ends[ended] <= start) {
                ended++;
                rooms--;
            }
            rooms++; // This meeting takes a room.
            best = Math.max(best, rooms);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(minMeetingRooms(new int[][] {{0, 30}, {5, 10}, {15, 20}})); // 2
        System.out.println(minMeetingRooms(new int[][] {{7, 10}, {2, 4}})); // 1
        System.out.println(minMeetingRooms(new int[][] {{1, 5}, {5, 10}, {10, 15}})); // 1
        System.out.println(minMeetingRooms(new int[][] {{1, 10}, {2, 7}, {3, 19}, {8, 12}, {10, 20}, {11, 30}})); // 4
    }
}

Common Pitfalls

  • Scanning without sorting first. The one-pass merge only works because sorting by start puts every overlap right next to the block it joins.
  • Setting the merged end to the new interval's end instead of the larger of the two. [1, 10] followed by [2, 3] would shrink to [1, 3].
  • Comparing each interval with the previous input interval instead of the merged block. In [1, 10], [2, 3], [4, 5], the last one doesn't overlap [2, 3], but it does overlap [1, 10].
  • Getting the boundary wrong. Decide whether touching intervals like [1, 4] and [4, 5] overlap in this problem, then use <= or < to match.

Practice

More problems to try on your own.