Merge Intervals Problem Explained — Sorting, Overlaps & Edge Cases
- Sort by start time first — this single step transforms an O(n^2) brute force into an O(n log n) single-pass solution and is the entire reason the greedy approach works.
- The overlap condition is
currentStart <= lastMergedEnd(strict: they overlap or touch). UseMath.max()on the end — never a plain assignment — to handle fully contained intervals correctly. - The free-slot finder is the natural inverse of merge intervals: after merging busy blocks, the gaps between them are your free time. This pattern shows up in calendar apps, scheduling systems, and bandwidth allocation.
- Sort by start time: O(n log n). This is mandatory — without it, you need O(n^2) comparisons.
- Overlap condition: currentStart <= lastEnd. Use strict < for non-overlap check.
- Merge: update lastEnd = max(lastEnd, currentEnd). Never assign directly.
- Time: O(n log n). Space: O(n) for output list.
- Calendar apps merge busy slots to show free time.
- Database query optimizers merge overlapping index range scans.
- Firewall engines merge CIDR blocks before evaluating packet rules.
- Forgetting Math.max() when extending the merged end. A contained interval like [2,5] inside [1,10] shrinks the end to 5 instead of keeping 10.
Merged result contains overlapping intervals.
Print sort order: System.out.println(Arrays.deepToString(intervals)) — verify intervals are sorted by index 0Test with unsorted input [[3,4],[1,2],[5,6]] — expected [[1,2],[3,4],[5,6]]Touching intervals not merged ([1,4],[4,7] stays as two intervals).
Print the condition: System.out.println("lastEnd=" + lastEnd + " currentStart=" + currentStart + " overlap=" + (lastEnd >= currentStart))If lastEnd == currentStart and overlap is false, the condition uses <= instead of <Contained interval shrinks merged end ([1,10] + [2,5] → [1,5] instead of [1,10]).
Test with [[1,10],[2,5]] — expected [[1,10]]If result is [[1,5]], the merge assigns currentEnd instead of max(lastEnd, currentEnd)Result is corrupted after caller modifies input.
Print identity: System.out.println(result[0] == intervals[0]) — if true, same referenceModify input after merge and check if result changesProduction Incident
Production Debug GuideSymptom-first investigation path for interval merging bugs.
Interval merging is a foundational pattern in calendar systems, database query optimizers, network firewalls, and resource schedulers. Every system that deals with overlapping time ranges or numeric spans uses some variant of this algorithm.
The problem: given an unsorted list of intervals, collapse all overlapping pairs into consolidated ranges. The naive approach compares every pair: O(n^2). The optimal approach sorts by start time first, then merges in a single linear pass: O(n log n). The sort is the entire secret — it transforms the problem from pairwise comparison to sequential merging.
The common misconception is that the merge logic itself is the hard part. It is not. The merge is a simple one-line check: if currentStart <= lastEnd, update lastEnd = max(lastEnd, currentEnd). The hard part is recognizing that sorting by start time makes this single-pass approach correct. Without the sort, a later interval could overlap an earlier one that was already processed.
Worked Example — Merging Overlapping Intervals
Intervals: [[1,3],[2,6],[8,10],[15,18]].
- Sort by start time: already sorted → [[1,3],[2,6],[8,10],[15,18]].
- merged = [[1,3]]. Compare [2,6]: start=2 <= last_end=3, so merge → update last to [1,6].
- Compare [8,10]: start=8 > last_end=6, no overlap → append [8,10]. merged=[[1,6],[8,10]].
- Compare [15,18]: start=15 > last_end=10, no overlap → append. merged=[[1,6],[8,10],[15,18]].
- Result: [[1,6],[8,10],[15,18]].
For insert-interval [[1,5],[6,9]] with new interval [2,7]: 1. Add all intervals ending before new.start=2: [1,5] ends at 5 which is >= 2, skip. 2. Merge all overlapping: [1,5] and [2,7] → [1,7]; [6,9] start=6 <= 7 → merge to [1,9]. 3. Add remaining: none. Result: [[1,9]].
package io.thecodeforge.algo; import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class WorkedExampleMergeIntervals { public static int[][] merge(int[][] intervals) { if (intervals == null || intervals.length == 0) return new int[0][0]; Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); List<int[]> merged = new ArrayList<>(); merged.add(new int[]{intervals[0][0], intervals[0][1]}); for (int i = 1; i < intervals.length; i++) { int[] last = merged.get(merged.size() - 1); if (intervals[i][0] <= last[1]) { last[1] = Math.max(last[1], intervals[i][1]); } else { merged.add(new int[]{intervals[i][0], intervals[i][1]}); } } return merged.toArray(new int[merged.size()][]); } public static void main(String[] args) { int[][] intervals = {{1,3},{2,6},{8,10},{15,18}}; System.out.println("Input: " + Arrays.deepToString(intervals)); System.out.println("Merged: " + Arrays.deepToString(merge(intervals))); } }
Merged: [[1, 6], [8, 10], [15, 18]]
- Sort by start time: O(n log n). This is the key that makes the greedy approach work.
- Merge: if currentStart <= lastEnd, update lastEnd = max(lastEnd, currentEnd).
- Non-overlap: currentStart > lastEnd (strict). Append new interval.
- The sort guarantees that if the current interval doesn't overlap the last merged one, it doesn't overlap any earlier one.
- Most interval problems are variants of this pattern: insert interval, meeting rooms, free slots.
How Merge Intervals Works — Plain English and Algorithm
Given a list of intervals, merge all overlapping ones into consolidated intervals. Two intervals [a,b] and [c,d] overlap if c <= b (the second starts before or when the first ends).
Algorithm: 1. Sort intervals by their start time: O(n log n). 2. Initialize result with the first interval. 3. For each subsequent interval [start, end]: a. If start <= result[-1][1]: the current interval overlaps the last merged interval. Update result[-1][1] = max(result[-1][1], end). b. Else: no overlap. Append [start, end] to result. 4. Return result.
Worked example — merge [[1,3],[2,6],[8,10],[15,18]]: Sort: already sorted. result = [[1,3]]. [2,6]: 2<=3, overlap. Update result[-1] end to max(3,6)=6. result=[[1,6]]. [8,10]: 8>6, no overlap. Append. result=[[1,6],[8,10]]. [15,18]: 15>10, no overlap. Append. result=[[1,6],[8,10],[15,18]]. Final: [[1,6],[8,10],[15,18]].
package io.thecodeforge.algo; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.List; public class MergeIntervalsAlgorithm { /** * Merges all overlapping intervals. O(n log n) time, O(n) space. */ public static int[][] merge(int[][] intervals) { if (intervals == null || intervals.length == 0) return new int[0][0]; // Step 1: Sort by start time — overflow-safe comparator Arrays.sort(intervals, Comparator.comparingInt(a -> a[0])); List<int[]> result = new ArrayList<>(); for (int[] interval : intervals) { // Step 2: Check overlap with last merged interval if (result.isEmpty() || result.get(result.size() - 1)[1] < interval[0]) { // No overlap — append new interval (defensive copy) result.add(new int[]{interval[0], interval[1]}); } else { // Overlap — extend the end of the last merged interval result.get(result.size() - 1)[1] = Math.max(result.get(result.size() - 1)[1], interval[1]); } } return result.toArray(new int[result.size()][]); } public static void main(String[] args) { int[][] intervals = {{1,3},{2,6},{8,10},{15,18}}; System.out.println("Merged: " + Arrays.deepToString(merge(intervals))); // Edge cases System.out.println("Empty: " + Arrays.deepToString(merge(new int[0][0]))); System.out.println("Single: " + Arrays.deepToString(merge(new int[][]{{3,7}}))); System.out.println("Touching: " + Arrays.deepToString(merge(new int[][]{{1,4},{4,7}}))); System.out.println("Contained: " + Arrays.deepToString(merge(new int[][]{{1,10},{2,5}}))); } }
Empty: []
Single: [[3, 7]]
Touching: [[1, 7]]
Contained: [[1, 10]]
- a[0] - b[0]: overflows on extreme values. Wrong sort order.
- Integer.compare(a[0], b[0]): overflow-safe. Correct sort order.
- Comparator.comparingInt(a -> a[0]): overflow-safe, readable, recommended.
- In production: always use Integer.compare or Comparator.comparingInt.
- In interviews: mention the overflow risk to signal production awareness.
Why Sorting First Is the Entire Secret to This Problem
Here's the most have to compare every interval against every other interval — that's O(n²) comparisons. Sort first by start time and suddenly you only ever need to look at the PREVIOUS merged interval. Why? Because once intervals are sorted by start, if the current interval's start is beyond the previous interval's end, no future interval can possibly overlap the previous one either. You can commit to that merge and move on.
Think of it like sorting your mail by date before filing. Once you've sorted it, you can walk through the pile once, stacking letters that belong in the same date range together, and never look backwards.
The overlap condition itself is: two intervals [a, b] and [c, d] overlap if and only if c <= b. That is, the new interval starts BEFORE or exactly when the current one ends. When they overlap, the merged interval is [a, max(b, d)] — you keep the earlier start and push the end out as far as needed. The max() call is critical important insight in this whole article: without sorting, you'd because the new interval might be entirely contained inside the existing one.
package io.thecodeforge.algo; import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class MergeIntervals { public static int[][] merge(int[][] intervals) { // Step 1: Sort by start time — this is the key that makes the whole // algorithm work in a single linear pass afterward. Arrays.sort(intervals, (firstInterval, secondInterval) -> Integer.compare(firstInterval[0], secondInterval[0]) ); List<int[]> mergedList = new ArrayList<>(); for (int[] currentInterval : intervals) { if (mergedList.isEmpty() || mergedList.get(mergedList.size() - 1)[1] < currentInterval[0]) { mergedList.add(new int[]{currentInterval[0], currentInterval[1]}); } else { int[] lastMerged = mergedList.get(mergedList.size() - 1); lastMerged[1] = Math.max(lastMerged[1], currentInterval[1]); } } return mergedList.toArray(new int[mergedList.size()][]); } public static void main(String[] args) { int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}}; System.out.println("Merged: " + Arrays.deepToString(merge(intervals))); } }
- Sort by start: ensures intervals are processed in start-time order.
- Greedy invariant: if current.start > lastMerged.end, no earlier interval can overlap current.
- Proof: lastMerged.end >= all earlier intervals' ends (because merging extends the end).
- If current.start > lastMerged.end, then current.start > all earlier ends. No overlap possible.
- This is why sorting is mandatory — without it, the greedy invariant breaks.
Handling the Sneaky Edge Cases That Trip Up Most Candidates
The basic algorithm handles obvious overlaps, but interviews are won or lost on edge cases. There are three you need to have cold.
FIRST: Touching intervals. Do [1,4] and [4,7] overlap? That depends on the problem definition. The standard LeetCode version treats touching as overlapping, meaning [1,4] and [4,7] become [1,7]. Our condition lastEnd < currentStart handles this correctly — if they're equal (touching), the condition is false, so they merge. Make sure you're using strict less-than, not less-than-or-equal.
SECOND: A fully contained interval. If you have [1,10] followed by [2,5], the second is completely swallowed by the first. The Math.max() call saves you here — max(10,5) correctly keeps 10 as the end.
THIRD: A single interval input, or an empty array. Both are handled naturally by the loop — empty input returns empty output, single input goes straight into mergedList and comes back unchanged. Always test your solution with these before an interview.
FOURTH (the real trap): an already-sorted input with no overlaps at all. Every interval gets added independently. This is the worst case for interview candidates who hard-code assumptions about input state.
package io.thecodeforge.algo; import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class MergeIntervalsEdgeCases { public static int[][] merge(int[][] intervals) { if (intervals == null || intervals.length == 0) { return new int[0][0]; } Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); List<int[]> mergedList = new ArrayList<>(); for (int[] currentInterval : intervals) { if (mergedList.isEmpty() || mergedList.get(mergedList.size() - 1)[1] < currentInterval[0]) { mergedList.add(new int[]{currentInterval[0], currentInterval[1]}); } else { mergedList.get(mergedList.size() - 1)[1] = Math.max(mergedList.get(mergedList.size() - 1)[1], currentInterval[1]); } } return mergedList.toArray(new int[mergedList.size()][]); } public static void printResult(String label, int[][] result) { System.out.print(label + ": "); for (int[] interval : result) { System.out.print("[" + interval[0] + "," + interval[1] + "] "); } System.out.println(); } public static void main(String[] args) { printResult("Touching [1,4],[4,7]", merge(new int[][]{{1, 4}, {4, 7}})); printResult("Contained [1,10],[2,5]", merge(new int[][]{{1, 10}, {2, 5}})); printResult("Single [3,7]", merge(new int[][]{{3, 7}})); printResult("No overlap [1,2],[3,4],[5,6]", merge(new int[][]{{1, 2}, {3, 4}, {5, 6}})); printResult("Full collapse [1,4],[2,5],[3,6]", merge(new int[][]{{1, 4}, {2, 5}, {3, 6}})); } }
Contained [1,10],[2,5]: [1,10]
Single [3,7]: [3,7]
No overlap [1,2],[3,4],[5,6]: [1,2] [3,4] [5,6]
Full collapse [1,4],[2,5],[3,6]: [1,6]
mergedList.add(currentInterval), you're adding the original array reference. If the caller modifies the input after calling merge(), your results silently corrupt. Add new int[]{currentInterval[0], currentInterval[1]} instead to store a defensive copy — this is the difference between a junior and production-quality solution.Real-World Patterns — Where Merge Intervals Actually Shows Up in Production
Understanding a problem in isolation is only half the job. Knowing when to reach for this pattern in the wild is what separates a strong engineer from someone who just passed LeetCode.
CALENDAR & SCHEDULING: Any system that shows you free/busy time blocks merges intervals under the hood. When you check someone's availability in Google Calendar, it collapses all their overlapping events before showing you the gaps.
DATABASE INDEX SCANS: Query optimizers merge overlapping range scans on indexed columns. If you ask for rows where age between 20 and 40, AND separately where age between 35 and 55, the engine merges these into one scan from 20 to 55.
NETWORK & SECURITY: Firewall rules often specify IP ranges. Before applying rules, systems merge overlapping CIDR blocks to reduce the number of rules evaluated per packet.
VIDEO/AUDIO EDITING: Timelines merge overlapping clips or subtitle ranges. Any NLE (non-linear editor) uses this when you apply a fade to overlapping audio regions.
The variant problems you'll encounter include: finding the total length covered by all intervals (sum of merged lengths), finding the gaps between merged intervals (invert the merged list), and the insert interval problem (insert a new interval and re-merge).
package io.thecodeforge.algo; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.List; /** * Real-world use case: Given a person's busy calendar slots, * find all the FREE gaps in their day between 9am and 6pm. */ public class CalendarFreeSlotFinder { private static int[][] mergeBusySlots(int[][] busySlots) { if (busySlots.length == 0) return new int[0][0]; Arrays.sort(busySlots, Comparator.comparingInt(a -> a[0])); List<int[]> consolidated = new ArrayList<>(); for (int[] slot : busySlots) { if (consolidated.isEmpty() || consolidated.get(consolidated.size() - 1)[1] < slot[0]) { consolidated.add(new int[]{slot[0], slot[1]}); } else { consolidated.get(consolidated.size() - 1)[1] = Math.max(consolidated.get(consolidated.size() - 1)[1], slot[1]); } } return consolidated.toArray(new int[consolidated.size()][]); } public static List<int[]> findFreeSlots( int[][] busySlots, int workdayStart, int workdayEnd) { int[][] mergedBusy = mergeBusySlots(busySlots); List<int[]> freeSlots = new ArrayList<>(); int freeStart = workdayStart; for (int[] busyBlock : mergedBusy) { if (freeStart < busyBlock[0]) { freeSlots.add(new int[]{freeStart, busyBlock[0]}); } freeStart = Math.max(freeStart, busyBlock[1]); } if (freeStart < workdayEnd) { freeSlots.add(new int[]{freeStart, workdayEnd}); } return freeSlots; } public static void main(String[] args) { int[][] alexBusySlots = { {9, 10}, {9, 11}, {13, 14}, {14, 15}, {16, 18} }; List<int[]> freeSlots = findFreeSlots(alexBusySlots, 9, 18); System.out.println("Alex's free slots today:"); for (int[] slot : freeSlots) { System.out.println(" " + slot[0] + ":00 - " + slot[1] + ":00"); } } }
11:00 - 13:00
15:00 - 16:00
- Step 1: Merge each person's busy slots independently.
- Step 2: Find free slots for each person (gaps between merged busy slots).
- Step 3: Find intersection of the two free-slot lists. This is another interval problem.
- Alternative: merge both persons' busy slots together, then find gaps. Simpler but less flexible.
- The pattern composes: merge → invert → intersect. Each step is an interval operation.
| Aspect | Without Sorting (Brute Force) | Sort First (Optimal) | Sort by End Time (Wrong) |
|---|---|---|---|
| Time Complexity | O(n^2) — compare every pair | O(n log n) — sort + one linear pass | O(n log n) — sort + one linear pass |
| Space Complexity | O(n) result list | O(n) result list | O(n) result list |
| Passes Required | Multiple passes over all intervals | Single pass after sorting | Single pass after sorting |
| Correctness Risk | High — easy to miss non-adjacent overlaps | Low — sorted order guarantees adjacency | High — greedy invariant broken |
| Code Complexity | High — complex nested loop logic | Low — clean, readable single loop | Low — looks correct but produces wrong results |
| Handles Unsorted Input | Yes, but slowly | Yes — sort step handles it explicitly | Yes — but produces wrong merged intervals |
| Interview Acceptability | Will fail for n > ~100 in time-limited tests | Standard expected solution | Will be rejected — sort by start, not end |
| Greedy Invariant | N/A — no invariant | current.start > lastMerged.end implies no earlier overlap | Broken — lastMerged.end is not >= all earlier ends |
🎯 Key Takeaways
- Sort by start time first — this single step transforms an O(n^2) brute force into an O(n log n) single-pass solution and is the entire reason the greedy approach works.
- The overlap condition is
currentStart <= lastMergedEnd(strict: they overlap or touch). UseMath.max()on the end — never a plain assignment — to handle fully contained intervals correctly. - The free-slot finder is the natural inverse of merge intervals: after merging busy blocks, the gaps between them are your free time. This pattern shows up in calendar apps, scheduling systems, and bandwidth allocation.
- In production code, add a defensive copy when inserting into the result list (
new int[]{start, end}) to prevent input mutation from silently corrupting your output. - Sort by start time, never by end time. Sort-by-end breaks the greedy invariant and produces wrong results on inputs with long early-starting intervals.
- Use Integer.compare or Comparator.comparingInt for overflow-safe sorting. Subtraction-based comparators overflow on extreme values.
- Test with: touching intervals [1,4],[4,7], contained interval [1,10],[2,5], empty input, single interval, and no-overlap input.
- The pattern composes: merge → invert (free slots) → intersect (common free time). you process later has a start time >= all previous starts. If the current interval doesn't overlap with doesn't it work to just check if the current interval overlaps Each step is an interval operation.
⚠ Common Mistakes to Avoid
Interview Questions on This Topic
- QCan you walk me through your merge intervals solution and explain why you sort first? What's the time complexity of the sort step, and is there any way to avoid it?
- QGiven two people's meeting schedules and the bounds of their working day, find all time slots where both are free for at least 30 minutes. How does your merge intervals logic apply here?
- QWhat changes in your algorithm if the problem asks you to count the number of intervals that are removed (merged away), rather than returning the merged list? And what if overlapping at exactly one endpoint should NOT merge — how does your overlap condition change?
- QHow would you insert a new interval into a sorted list of non-overlapping intervals and re-merge? What is the time complexity?
- QExplain the greedy correctness proof for sort-then-merge. Why does sorting by start time make the single-pass approach correct?
- QYour merge function stores references to the original input arrays. The caller modifies the input after the merge. What happens and how do you fix it?
- QHow would you find the total length covered by all merged intervals? What about the gaps between them?
- QSort-by-end produces wrong results on [[1,10],[2,3],[4,5]]. Trace the algorithm and explain why the greedy invariant breaks.
- QHow would you merge intervals in a streaming context where intervals arrive one at a time and you need to maintain the merged result incrementally?
- QDescribe a production scenario where merge intervals was critical. What edge cases did you encounter and what was the performance impact?
Frequently Asked Questions
What is the time complexity of the merge intervals algorithm?
The overall time complexity is O(n log n), dominated by the sorting step. The subsequent merging pass is O(n) — each interval is visited exactly once. Space complexity is O(n) for the output list, or O(log n) if you consider only auxiliary space and exclude the output.
Should touching intervals like [1,4] and [4,7] be merged into [1,7]?
In the standard LeetCode definition (problem 56), yes — touching intervals are merged because they share the point 4. Your non-overlap condition should be a strict less-than: lastEnd < currentStart. If the problem explicitly states intervals are open (not including endpoints), you'd switch to less-than-or-equal.
Why with ALL previously merged intervals?
Once you sort by start time, you never need to check earlier intervals. Any interval the most recently merged one (the one with the furthest-right end), it can't possibly overlap with any earlier one either — those ended even sooner. This is the greedy insight that makes the single-pass approach valid.
What if intervals are not sorted?
Always sort by start time first. The sorting step is O(n log n) and is mandatory — without it, a later interval could overlap an earlier one that was already processed and added to results, which the algorithm would miss.
How do you find the insertion position of a new interval into sorted non-overlapping intervals?
Binary search for the first interval whose start > new interval's start. Then merge with any overlapping neighbours on both sides. This is the 'insert interval' variant, solved in O(n) by scanning left and right from the insertion point.
Why do we sort by start time before merging?
Sorting ensures that if interval A starts before interval B, then A.end compared to B.start tells us definitively whether they overlap. Without sorting, an interval that starts later could overlap a much earlier interval, requiring O(n^2) checks instead of a single linear pass.
How do we handle the case where one interval completely contains another?
When merging, the new end is max(current_end, next_interval_end), not just next_interval_end. So [[1,10],[2,5]]: compare [2,5] to [1,10]; start=2 <= end=10 so merge, new end = max(10,5) = 10. Result: [[1,10]], correctly swallowing the contained interval.
What happens if you sort by end time instead of start time?
The greedy invariant breaks. With sort-by-end, the processing order may be [2,3], [4,5], [1,10]. The algorithm compares [1,10] only against [4,5] (the last merged), merges to [4,10], and misses the overlap with [2,3]. The result is [[2,3],[4,10]] instead of the correct [[1,10]]. Always sort by start time.
Developer and founder of TheCodeForge. I built this site because I was tired of tutorials that explain what to type without explaining why it works. Every article here is written to make concepts actually click.