Merge intervals pattern questions with worked solutions
Last updated 2026-11-19
The merge intervals pattern is about combining ranges. Sort by start, walk through, and either extend the current merged range or start a new one. Once you can merge, a surprising number of problems become variations: inserting an interval, finding intersections of two lists, summarising runs of numbers, finding free time as the gaps between merged busy periods, or marking text ranges.
This page is a deep dive on that family only. Questions about attendance, room counts and choosing the maximum compatible set are on the companion interval questions page. Sorting background is in sorting algorithms questions, and the DSA coding round guide shows how pattern questions appear in tests.
| Problems | 11, easy to hard |
|---|---|
| Languages | Python and Java |
| Core loop | Sort by start; extend with max end or append |
The core loop
Sort by start. Keep an output list. For each interval, if the output is empty or the interval starts after the last output interval ends, append it; otherwise set the last end to the maximum of the two ends. The max matters: a long interval can swallow shorter ones that follow.
For integer ranges where adjacent ranges such as [1,2] and [3,4] should become [1,4], compare with end + 1. For continuous ranges, compare with end.
- Merge: sort then extend or append.
- Insert into a sorted list: copy the left part, merge the overlap, copy the right part, with no sort needed.
- Gaps: the space between one merged end and the next start.
- Two sorted lists: advance the pointer whose interval ends first.
Edge cases that decide marks
Empty input, a single interval, intervals fully contained in others, identical intervals, intervals that touch at one point, and unsorted input. Also mutating the input list: when the interface expects a new list, copy rather than edit.
Merge intervals pattern questions with worked solutions: questions with worked answers
1 Merge overlapping intervals.
mediumSort by start. Compare each interval with the last merged one: if it starts at or before that end, they overlap, so extend the end to the larger of the two; otherwise append a new interval. For [[1,3],[2,6],[8,10],[15,18]] the result is [[1,6],[8,10],[15,18]]. Time O(n log n) for the sort, space O(n) for the output.. Edge cases: empty input, one interval, a long interval covering many (use max), touching intervals [1,4] and [4,5] (merged).
pythondef merge(iv): iv.sort(key=lambda x: x[0]) out = [] for s, e in iv: if out and s <= out[-1][1]: out[-1][1] = max(out[-1][1], e) else: out.append([s, e]) return outjavaimport java.util.*; class Solution { static int[][] merge(int[][] iv) { Arrays.sort(iv, (a, b) -> Integer.compare(a[0], b[0])); List<int[]> out = new ArrayList<>(); for (int[] x : iv) { if (!out.isEmpty() && x[0] <= out.get(out.size() - 1)[1]) out.get(out.size() - 1)[1] = Math.max(out.get(out.size() - 1)[1], x[1]); else out.add(new int[]{x[0], x[1]}); } return out.toArray(new int[0][]); } }2 Merge integer ranges where touching ranges such as [1,2] and [3,4] also count as one.
easyInteger ranges are inclusive, so [1,2] and [3,4] cover 1 through 4 with no gap. Use the same merge loop but compare the next start with the current end plus one. Without that, adjacent ranges stay separate and the answer looks wrong. Time O(n log n), space O(n).. Edge cases: adjacent ranges, a gap of exactly one missing integer (not merged), empty input.
pythondef merge_inclusive(iv): iv.sort(key=lambda x: x[0]) out = [] for s, e in iv: if out and s <= out[-1][1] + 1: out[-1][1] = max(out[-1][1], e) else: out.append([s, e]) return outjavaimport java.util.*; class Solution { static int[][] mergeInclusive(int[][] iv) { Arrays.sort(iv, (a, b) -> Integer.compare(a[0], b[0])); List<int[]> out = new ArrayList<>(); for (int[] x : iv) { if (!out.isEmpty() && x[0] <= out.get(out.size() - 1)[1] + 1) out.get(out.size() - 1)[1] = Math.max(out.get(out.size() - 1)[1], x[1]); else out.add(new int[]{x[0], x[1]}); } return out.toArray(new int[0][]); } }3 Insert a new interval into a sorted list of non-overlapping intervals and merge as needed.
mediumNo sorting is needed because the list is already sorted. Copy all intervals that end before the new one starts. Then, for every interval that starts at or before the new end, absorb it by taking the minimum start and maximum end. Append the merged interval, then copy the remaining intervals. Time O(n), space O(n).. Edge cases: empty list, new interval before or after everything, new interval covering all of them.
pythondef insert(iv, new): res, i, n = [], 0, len(iv) while i < n and iv[i][1] < new[0]: res.append(iv[i]) i += 1 while i < n and iv[i][0] <= new[1]: new = [min(new[0], iv[i][0]), max(new[1], iv[i][1])] i += 1 res.append(new) res.extend(iv[i:]) return resjavaimport java.util.*; class Solution { static int[][] insert(int[][] iv, int[] nw) { List<int[]> res = new ArrayList<>(); int i = 0, n = iv.length; while (i < n && iv[i][1] < nw[0]) res.add(iv[i++]); while (i < n && iv[i][0] <= nw[1]) { nw = new int[]{Math.min(nw[0], iv[i][0]), Math.max(nw[1], iv[i][1])}; i++; } res.add(nw); while (i < n) res.add(iv[i++]); return res.toArray(new int[0][]); } }4 Summary ranges: compress a sorted array of unique integers into ranges like "0->2".
easyWalk through the array and start a range at index start. When the next element is not the current plus one (or the array ends), close the range: print "a->b" if it spans more than one value, else just "a". This is merge intervals with each number as the interval [x, x]. Time O(n), space O(1) beyond the output.. Edge cases: empty array, no consecutive numbers, one long run, negative numbers.
pythondef summary_ranges(a): res, start = [], 0 for i in range(len(a)): if i == len(a) - 1 or a[i + 1] != a[i] + 1: res.append(str(a[start]) if start == i else f"{a[start]}->{a[i]}") start = i + 1 return resjavaimport java.util.*; class Solution { static List<String> summaryRanges(int[] a) { List<String> res = new ArrayList<>(); int start = 0; for (int i = 0; i < a.length; i++) { if (i == a.length - 1 || a[i + 1] != a[i] + 1) { res.add(start == i ? String.valueOf(a[start]) : a[start] + "->" + a[i]); start = i + 1; } } return res; } }5 Partition labels: split a string so each letter appears in at most one part, with as many parts as possible.
mediumEach letter defines an interval from its first to its last occurrence, and parts are the merged intervals. Record the last index of each letter. Scan, extending the current part end to the farthest last index seen; when the scan index reaches that end, close the part and record its length. Time O(n), space O(alphabet).. Edge cases: all letters distinct (each its own part), one letter repeated (a single part), empty string.
pythondef partition_labels(s): last = {c: i for i, c in enumerate(s)} res, start, end = [], 0, 0 for i, c in enumerate(s): end = max(end, last[c]) if i == end: res.append(end - start + 1) start = i + 1 return resjavaimport java.util.*; class Solution { static List<Integer> partitionLabels(String s) { int[] last = new int[26]; for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i; List<Integer> res = new ArrayList<>(); int start = 0, end = 0; for (int i = 0; i < s.length(); i++) { end = Math.max(end, last[s.charAt(i) - 'a']); if (i == end) { res.add(end - start + 1); start = i + 1; } } return res; } }6 Interval list intersections: the overlaps between two sorted lists of disjoint intervals.
mediumUse two pointers. The intersection of the current pair is [max(starts), min(ends)] and is valid when that start does not exceed that end. Then advance the pointer whose interval ends first, since it cannot overlap anything later in the other list. Time O(n + m), space O(1) beyond the output.. Edge cases: either list empty, overlaps touching at a single point (a one-point interval), one interval spanning many.
pythondef interval_intersection(a, b): i = j = 0 res = [] while i < len(a) and j < len(b): lo = max(a[i][0], b[j][0]) hi = min(a[i][1], b[j][1]) if lo <= hi: res.append([lo, hi]) if a[i][1] < b[j][1]: i += 1 else: j += 1 return resjavaimport java.util.*; class Solution { static int[][] intervalIntersection(int[][] a, int[][] b) { List<int[]> res = new ArrayList<>(); int i = 0, j = 0; while (i < a.length && j < b.length) { int lo = Math.max(a[i][0], b[j][0]), hi = Math.min(a[i][1], b[j][1]); if (lo <= hi) res.add(new int[]{lo, hi}); if (a[i][1] < b[j][1]) i++; else j++; } return res.toArray(new int[0][]); } }7 Union of two sorted lists of disjoint intervals.
mediumMerge the two lists by start time with two pointers, picking whichever next interval starts earlier, and apply the usual merge rule against the last interval in the output. This avoids re-sorting the combined list, so it is linear rather than O(n log n). Time O(n + m), space O(n + m).. Edge cases: one list empty, nested intervals across lists, equal starts.
pythondef union_sorted(a, b): i = j = 0 out = [] while i < len(a) or j < len(b): if j >= len(b) or (i < len(a) and a[i][0] <= b[j][0]): s, e = a[i] i += 1 else: s, e = b[j] j += 1 if out and s <= out[-1][1]: out[-1][1] = max(out[-1][1], e) else: out.append([s, e]) return outjavaimport java.util.*; class Solution { static int[][] unionSorted(int[][] a, int[][] b) { List<int[]> out = new ArrayList<>(); int i = 0, j = 0; while (i < a.length || j < b.length) { int[] cur; if (j >= b.length || (i < a.length && a[i][0] <= b[j][0])) cur = a[i++]; else cur = b[j++]; if (!out.isEmpty() && cur[0] <= out.get(out.size() - 1)[1]) out.get(out.size() - 1)[1] = Math.max(out.get(out.size() - 1)[1], cur[1]); else out.add(new int[]{cur[0], cur[1]}); } return out.toArray(new int[0][]); } }8 Total length covered by the union of a set of intervals.
easySort by start and sweep, keeping the current merged range. When the next interval starts after the current end, add the finished range length to the total and start a new range; otherwise extend the end to the larger value. Add the last range at the end. Overlaps are counted once. Time O(n log n), space O(1).. Edge cases: empty input (0), nested intervals, touching intervals (no gap, length adds correctly).
pythondef covered_length(iv): if not iv: return 0 iv.sort() total = 0 cs, ce = iv[0] for s, e in iv[1:]: if s > ce: total += ce - cs cs, ce = s, e else: ce = max(ce, e) return total + ce - csjavaimport java.util.*; class Solution { static int coveredLength(int[][] iv) { if (iv.length == 0) return 0; Arrays.sort(iv, (a, b) -> Integer.compare(a[0], b[0])); int total = 0, cs = iv[0][0], ce = iv[0][1]; for (int i = 1; i < iv.length; i++) { if (iv[i][0] > ce) { total += ce - cs; cs = iv[i][0]; ce = iv[i][1]; } else ce = Math.max(ce, iv[i][1]); } return total + ce - cs; } }9 Add bold tags: wrap every substring of s that matches a word in a dictionary, merging overlapping or adjacent matches.
hardEach match is an interval of character positions. Mark every matched position in a boolean array (equivalent to merging the intervals), then build the output by opening a bold tag where a run of marked positions starts and closing it where the run ends. Runs that touch are merged automatically because adjacent marked positions form a single run. Time O(n * total length of words) with simple find, space O(n).. Edge cases: no matches (unchanged string), overlapping matches, adjacent matches, words that are substrings of each other.
pythondef add_bold_tag(s, words): n = len(s) bold = [False] * n for w in words: i = s.find(w) while i != -1: for k in range(i, i + len(w)): bold[k] = True i = s.find(w, i + 1) out = [] for i, ch in enumerate(s): if bold[i] and (i == 0 or not bold[i - 1]): out.append("<b>") out.append(ch) if bold[i] and (i == n - 1 or not bold[i + 1]): out.append("</b>") return "".join(out)javaimport java.util.*; class Solution { static String addBoldTag(String s, String[] words) { int n = s.length(); boolean[] bold = new boolean[n]; for (String w : words) { int i = s.indexOf(w); while (i != -1) { for (int k = i; k < i + w.length(); k++) bold[k] = true; i = s.indexOf(w, i + 1); } } StringBuilder out = new StringBuilder(); for (int i = 0; i < n; i++) { if (bold[i] && (i == 0 || !bold[i - 1])) out.append("<b>"); out.append(s.charAt(i)); if (bold[i] && (i == n - 1 || !bold[i + 1])) out.append("</b>"); } return out.toString(); } }10 Employee free time: given each employee's sorted, disjoint busy intervals, find the time slots when everyone is free.
hardFlatten all busy intervals into one list and sort by start. Sweep while keeping the furthest end seen so far. Whenever the next interval starts after that end, the gap between them is free time for everyone. Gaps before the first start and after the last end are not counted. Time O(N log N) for N total intervals, space O(N).. Edge cases: a single employee, fully overlapping schedules (no free time), all schedules empty.
pythondef employee_free_time(schedule): iv = sorted((s, e) for emp in schedule for s, e in emp) if not iv: return [] out, end = [], iv[0][1] for s, e in iv[1:]: if s > end: out.append([end, s]) end = max(end, e) return outjavaimport java.util.*; class Solution { static List<int[]> employeeFreeTime(List<List<int[]>> schedule) { List<int[]> iv = new ArrayList<>(); for (List<int[]> emp : schedule) iv.addAll(emp); iv.sort((a, b) -> Integer.compare(a[0], b[0])); List<int[]> out = new ArrayList<>(); if (iv.isEmpty()) return out; int end = iv.get(0)[1]; for (int i = 1; i < iv.size(); i++) { int[] cur = iv.get(i); if (cur[0] > end) out.add(new int[]{end, cur[0]}); end = Math.max(end, cur[1]); } return out; } }11 Data stream as disjoint intervals: numbers arrive one at a time; report the current set as sorted disjoint ranges.
hardKeep a sorted structure keyed by range start. For a new value v, find the range that starts at or before v and the one that starts after v. If v is already covered, do nothing. Otherwise check whether v extends the left range (its end is v - 1), the right range (its start is v + 1), both (merge them) or neither (insert [v, v]). With a tree map each add is O(log n). Time O(log n) per add with a tree structure (the Python list insert is O(n)), space O(n).. Edge cases: a duplicate value, a value that bridges two ranges, values arriving in descending order.
pythonimport bisect class SummaryRanges: def __init__(self): self.iv = [] def add_num(self, v): iv = self.iv i = bisect.bisect_left(iv, [v]) if i > 0 and iv[i - 1][1] >= v: return if i < len(iv) and iv[i][0] == v: return left = i > 0 and iv[i - 1][1] == v - 1 right = i < len(iv) and iv[i][0] == v + 1 if left and right: iv[i - 1][1] = iv[i][1] del iv[i] elif left: iv[i - 1][1] = v elif right: iv[i][0] = v else: iv.insert(i, [v, v]) def get_intervals(self): return [x[:] for x in self.iv]javaimport java.util.*; class SummaryRanges { private final TreeMap<Integer, Integer> m = new TreeMap<>(); void addNum(int v) { Integer lo = m.floorKey(v), hi = m.higherKey(v); if (lo != null && m.get(lo) >= v) return; boolean left = lo != null && m.get(lo) == v - 1; boolean right = hi != null && hi == v + 1; if (left && right) { m.put(lo, m.get(hi)); m.remove(hi); } else if (left) m.put(lo, v); else if (right) { m.put(v, m.get(hi)); m.remove(hi); } else m.put(v, v); } int[][] getIntervals() { int[][] res = new int[m.size()][]; int i = 0; for (Map.Entry<Integer, Integer> e : m.entrySet()) res[i++] = new int[]{e.getKey(), e.getValue()}; return res; } }
Frequently asked questions
Why sort by start time when merging?
After sorting by start, any interval that overlaps the current merged range must come right after it, so a single left-to-right pass is enough. Without sorting you would need to compare every pair.
Why take the maximum of the two ends when merging?
A later interval can be completely inside the current merged one. Setting the end to the later interval end would shrink the range, so always take the larger end.
How do I handle touching intervals?
For continuous ranges such as time, [1,3] and [3,5] usually merge, so compare start with end using <=. For integer ranges where [1,2] and [3,4] should join, compare with end + 1.
Is insert interval O(n) or O(n log n)?
O(n) when the input list is already sorted and disjoint, as it is in the standard problem. If the input might be unsorted, sort first and the cost becomes O(n log n).
Where do room counts and scheduling belong?
They are interval decisions rather than merges. See interval questions and greedy questions.
Related guides
- Interval interview questions with worked solutions
- Sorting algorithm interview questions with worked solutions
- Greedy algorithm interview questions with worked solutions
- Two pointers interview questions with worked solutions
- Prefix sum interview questions with worked solutions
- Array interview questions with worked solutions
More in DSA Interview Questions
- Minimum Spanning Tree Interview Questions
- Monotonic stack interview questions with worked solutions
- Prefix sum interview questions with worked solutions
- Queue and deque interview questions with worked solutions
- Recursion interview questions with worked solutions
- Segment Tree Interview Questions
- Sliding window interview questions with worked solutions
- Sorting algorithm interview questions with worked solutions
- Stack interview questions with worked solutions
- String interview questions with worked solutions
- Top K elements interview questions with worked solutions
- Topological Sort Interview Questions