Dec 8, 2025

Intervals

Overview

Interval problems ask how ranges overlap, merge, or compete for resources. Sorting by start time supports merging, insertion, and concurrency tracking; sorting by end time supports greedy selection of the interval that leaves the most room for what follows.

Decide whether touching endpoints overlap before choosing < or <=. A linear scan is usually enough after sorting, while a min-heap is useful when the earliest active end or the next interval among several sorted schedules must be found repeatedly.

Templates

Merge: sort by start, compare with the result’s last end, then extend or append.
Insert: scan a sorted, disjoint list and place or merge the new interval once.
Concurrent intervals: sort by start and keep active end times in a min-heap.
Remove overlaps: sort by end and greedily keep the earliest finishing compatible interval.
Merge sorted schedules: put each schedule’s first interval in a min-heap, then push the next interval from the row just removed.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class IntervalTemplate {
	public static int[][] merge(int[][] intervals) {
		Arrays.sort(intervals, (first, second) ->
			Integer.compare(first[0], second[0])
		);
		List<int[]> res = new ArrayList<>();
		res.add(intervals[0]);

		for (int i = 1; i < intervals.length; i++) {
			int start = intervals[i][0];
			int end = intervals[i][1];

			if (res.get(res.size() - 1)[1] >= start) {
				int[] last = res.get(res.size() - 1);
				last[1] = Math.max(last[1], end);
			} else {
				res.add(new int[] {start, end});
			}
		}

		return res.toArray(new int[res.size()][]);
	}
}

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort()
    res = [intervals[0]]

    for i in range(1, len(intervals)):
        start, end = intervals[i]

        if res[-1][1] >= start:
            res[-1][1] = max(end, res[-1][1])
        else:
            res.append([start, end])

    return res

Problems

56. Merge Intervals

Combine every pair of overlapping intervals. Sort the intervals, initialize the result with the first one, then either extend the last merged end or append a new interval.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
	public int[][] merge(int[][] intervals) {
		Arrays.sort(intervals, (first, second) -> {
			int startComparison = Integer.compare(first[0], second[0]);
			return startComparison != 0
				? startComparison
				: Integer.compare(first[1], second[1]);
		});
		List<int[]> res = new ArrayList<>();
		res.add(intervals[0]);

		for (int i = 1; i < intervals.length; i++) {
			int start = intervals[i][0];
			int end = intervals[i][1];

			if (res.get(res.size() - 1)[1] >= start) {
				int[] last = res.get(res.size() - 1);
				last[1] = Math.max(end, last[1]);
			} else {
				res.add(new int[] {start, end});
			}
		}

		return res.toArray(new int[res.size()][]);
	}
}

from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        res = [intervals[0]]

        for i in range(1, len(intervals)):
            start, end = intervals[i]

            if res[-1][1] >= start:
                res[-1][1] = max(end, res[-1][1])
            else:
                res.append([start, end])

        return res

57. Insert Interval

Insert one interval into an already sorted, disjoint list with a merged flag. Before insertion, append intervals that end earlier, insert the new interval when it comes before the current one, or combine the first overlap. After insertion, merge any later overlap into the result’s last interval. No sorting is required, so the runtime is O(n).

import java.util.ArrayList;
import java.util.List;

class Solution {
	public int[][] insert(int[][] intervals, int[] newInterval) {
		List<int[]> res = new ArrayList<>();
		boolean merged = false;

		for (int[] interval : intervals) {
			int start = interval[0];
			int end = interval[1];

			if (!merged) {
				if (end < newInterval[0]) {
					res.add(new int[] {start, end});
				} else if (newInterval[1] < start) {
					res.add(newInterval);
					res.add(new int[] {start, end});
					merged = true;
				} else {
					res.add(new int[] {
						Math.min(start, newInterval[0]),
						Math.max(end, newInterval[1])
					});
					merged = true;
				}
			} else {
				int[] last = res.get(res.size() - 1);
				if (start <= last[1]) {
					last[1] = Math.max(end, last[1]);
				} else {
					res.add(new int[] {start, end});
				}
			}
		}

		if (!merged) {
			res.add(newInterval);
		}

		return res.toArray(new int[res.size()][]);
	}
}

from typing import List

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []
        merged = False

        for start, end in intervals:
            if not merged:
                if end < newInterval[0]:
                    res.append([start, end])
                elif newInterval[1] < start:
                    res.append(newInterval)
                    res.append([start, end])
                    merged = True
                else:
                    res.append([min(start, newInterval[0]), max(end, newInterval[1])])
                    merged = True
            else:
                if start <= res[-1][1]:
                    res[-1][1] = max(end, res[-1][1])
                else:
                    res.append([start, end])

        if not merged:
            res.append(newInterval)

        return res

253. Meeting Rooms II

The minimum number of rooms equals the maximum number of concurrent meetings. Sort meetings by start time and keep the end times of ongoing meetings in a min-heap. Before adding the current meeting, remove every meeting that has already ended; the largest heap size is the answer.

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
	public int minMeetingRooms(int[][] intervals) {
		Arrays.sort(intervals, (first, second) ->
			Integer.compare(first[0], second[0])
		);
		PriorityQueue<Integer> minHeap = new PriorityQueue<>();
		int res = 0;

		for (int[] interval : intervals) {
			int start = interval[0];
			int end = interval[1];

			while (minHeap.size() > 0 && minHeap.peek() <= start) {
				minHeap.poll();
			}
			minHeap.offer(end);
			res = Math.max(res, minHeap.size());
		}

		return res;
	}
}

import heapq
from typing import List

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        # min # of room required = max # of concurrent meetings
        # how to check on-going meetings?
        # for meetings started earlier than my current meeting
        # if they have not ended, then they are still on-going
        # keep a min_heap of meeting end times

        intervals.sort(key = lambda x : x[0])
        min_heap = []
        res = 0

        for start, end in intervals:
            while len(min_heap)>0 and min_heap[0] <= start:
                heapq.heappop(min_heap)
            heapq.heappush(min_heap, end)
            res = max(res, len(min_heap))

        return res

435. Non-overlapping Intervals

Remove the fewest intervals so the remainder do not overlap. Sort by end time and greedily keep the interval that finishes earliest, leaving the most room for future choices. Every interval starting before the last kept end is removed.

import java.util.Arrays;

class Solution {
	public int eraseOverlapIntervals(int[][] intervals) {
		Arrays.sort(intervals, (first, second) ->
			Integer.compare(first[1], second[1])
		);
		int removed = 0;
		int previousEnd = Integer.MIN_VALUE;

		for (int[] interval : intervals) {
			if (interval[0] < previousEnd) {
				removed++;
			} else {
				previousEnd = interval[1];
			}
		}

		return removed;
	}
}

from typing import List

class Solution:
	def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
		intervals.sort(key=lambda interval: interval[1])
		removed = 0
		previous_end = float("-inf")

		for start, end in intervals:
			if start < previous_end:
				removed += 1
			else:
				previous_end = end

		return removed

759. Employee Free Time

Merge the already sorted employee schedules with a min-heap. Each heap entry contains an interval and its row and column in schedule; after removing an interval, add the next interval from the same employee. Merge the resulting start-time order into combined busy intervals, then return every gap between consecutive busy intervals. For n intervals across k employees, this takes O(n log k) time.

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/*
class Interval {
	int start;
	int end;

	Interval(int start, int end) {
		this.start = start;
		this.end = end;
	}
}
*/

class Solution {
	private static class Entry {
		Interval interval;
		int row;
		int col;

		Entry(Interval interval, int row, int col) {
			this.interval = interval;
			this.row = row;
			this.col = col;
		}
	}

	public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
		PriorityQueue<Entry> heap = new PriorityQueue<>(
			(first, second) ->
				Integer.compare(first.interval.start, second.interval.start)
		);
		List<Interval> merged = new ArrayList<>();

		for (int idx = 0; idx < schedule.size(); idx++) {
			List<Interval> employee = schedule.get(idx);
			if (employee.size() > 0) {
				heap.offer(new Entry(employee.get(0), idx, 0));
			}
		}

		while (!heap.isEmpty()) {
			Entry entry = heap.poll();
			Interval interval = entry.interval;
			int row = entry.row;
			int col = entry.col;

			if (merged.size() == 0 ||
				merged.get(merged.size() - 1).end < interval.start) {
				merged.add(interval);
			} else {
				Interval last = merged.get(merged.size() - 1);
				last.end = Math.max(last.end, interval.end);
			}

			if (col + 1 < schedule.get(row).size()) {
				heap.offer(new Entry(
					schedule.get(row).get(col + 1),
					row,
					col + 1
				));
			}
		}

		List<Interval> res = new ArrayList<>();

		for (int i = 1; i < merged.size(); i++) {
			int start = merged.get(i - 1).end;
			int end = merged.get(i).start;
			res.add(new Interval(start, end));
		}

		return res;
	}
}

import heapq

# Definition for an Interval.
# class Interval:
#     def __init__(self, start: int = None, end: int = None):
#         self.start = start
#         self.end = end

class Solution:
    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':
        Interval.__lt__ = lambda self, other: self.start < other.start

        heap = []
        merged = []

        for idx, s in enumerate(schedule):
            if len(s) > 0:
                heap.append([s[0], idx, 0])

        heapq.heapify(heap)

        while heap:
            interval, row, col = heapq.heappop(heap)
            if len(merged) == 0 or merged[-1].end < interval.start:
                merged.append(interval)
            else:
                merged[-1].end = max(merged[-1].end, interval.end)
            if col + 1 < len(schedule[row]):
                heapq.heappush(heap, [schedule[row][col+1], row, col + 1])

        res = []

        for i in range(1, len(merged)):
            start = merged[i-1].end
            end = merged[i].start
            res.append(Interval(start, end))

        return res