Merge Intervals Problem Explained — Sorting, Overlaps & Edge Cases
Every calendar app, video editor timeline, database index optimizer, and network packet scheduler has one thing in common: they all deal with ranges that can overlap. When your Google Calendar shows you a conflict, or when a database engine merges index scans to avoid reading the same disk block twice, there's interval merging logic running underneath. This is not an academic exercise — it's production-grade logic that ships in real software every day.
The core problem is deceptively simple: you get an unsorted list of intervals like [[1,3],[2,6],[8,10],[15,18]] and you need to return [[1,6],[8,10],[15,18]] — all the overlapping pairs collapsed into single continuous ranges. The tricky part isn't the merging itself, it's recognizing WHEN two intervals overlap and doing it efficiently without accidentally skipping edge cases where intervals only touch at a single point.
By the end of this article you'll be able to implement the optimal O(n log n) solution from scratch, explain exactly why sorting is the non-negotiable first step, handle every edge case including touching intervals and fully contained intervals, and confidently answer the follow-up questions interviewers use to separate candidates who memorized a solution from those who actually understand it.
Why Sorting First Is the Entire Secret to This Problem
Here's the most important insight in this whole article: without sorting, you'd 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 because the new interval might be entirely contained inside the existing one.
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) -> firstInterval[0] - secondInterval[0] ); List<int[]> mergedList = new ArrayList<>(); for (int[] currentInterval : intervals) { // If the list is empty, or the current interval does NOT overlap // with the last merged interval, just add it as-is. if (mergedList.isEmpty() || mergedList.get(mergedList.size() - 1)[1] < currentInterval[0]) { mergedList.add(currentInterval); } else { // Overlap detected! Extend the END of the last merged interval // if needed. We use max() because the current interval might be // fully contained inside the last one (e.g. [1,10] and [2,5]). int[] lastMerged = mergedList.get(mergedList.size() - 1); lastMerged[1] = Math.max(lastMerged[1], currentInterval[1]); } } // Convert List<int[]> back to int[][] for the return type 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("Input intervals:"); for (int[] interval : intervals) { System.out.println(" [" + interval[0] + ", " + interval[1] + "]"); } int[][] merged = merge(intervals); System.out.println("\nMerged intervals:"); for (int[] interval : merged) { System.out.println(" [" + interval[0] + ", " + interval[1] + "]"); } } }
[1, 3]
[2, 6]
[8, 10]
[15, 18]
Merged intervals:
[1, 6]
[8, 10]
[15, 18]
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.
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]; // Guard clause: don't crash on empty input } 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) { // Case 1: Touching intervals — should merge into one printResult("Touching [1,4],[4,7]", merge(new int[][]{{1, 4}, {4, 7}})); // Case 2: Fully contained — outer interval swallows the inner one printResult("Contained [1,10],[2,5]", merge(new int[][]{{1, 10}, {2, 5}})); // Case 3: Single interval — should return it unchanged printResult("Single [3,7]", merge(new int[][]{{3, 7}})); // Case 4: No overlaps — all intervals returned as-is printResult("No overlap [1,2],[3,4],[5,6]", merge(new int[][]{{1, 2}, {3, 4}, {5, 6}})); // Case 5: All intervals collapse into one 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]
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).
import java.util.ArrayList; import java.util.Arrays; 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 (hours 9-18). */ public class CalendarFreeSlotFinder { // Merges overlapping busy slots into consolidated blocks private static int[][] mergeBusySlots(int[][] busySlots) { if (busySlots.length == 0) return new int[0][0]; Arrays.sort(busySlots, (a, b) -> Integer.compare(a[0], b[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()][]); } // Finds the free slots between the merged busy blocks within workday bounds public static List<int[]> findFreeSlots( int[][] busySlots, int workdayStart, int workdayEnd) { int[][] mergedBusy = mergeBusySlots(busySlots); List<int[]> freeSlots = new ArrayList<>(); int freeStart = workdayStart; // Cursor tracking where free time begins for (int[] busyBlock : mergedBusy) { int busyBlockStart = busyBlock[0]; int busyBlockEnd = busyBlock[1]; // If there's a gap between freeStart and the next busy block, it's free time if (freeStart < busyBlockStart) { freeSlots.add(new int[]{freeStart, busyBlockStart}); } // Move cursor past this busy block freeStart = Math.max(freeStart, busyBlockEnd); } // Check if there's free time between the last busy block and end of workday if (freeStart < workdayEnd) { freeSlots.add(new int[]{freeStart, workdayEnd}); } return freeSlots; } public static void main(String[] args) { // Alex's meetings today (hours in 24h format, e.g. 9 = 9am) int[][] alexBusySlots = { {9, 10}, // 9am–10am standup {9, 11}, // 9am–11am overlaps with standup (back-to-back block) {13, 14}, // 1pm–2pm lunch call {14, 15}, // 2pm–3pm back-to-back {16, 18} // 4pm–6pm late meeting }; int workdayStart = 9; // 9am int workdayEnd = 18; // 6pm List<int[]> freeSlots = findFreeSlots(alexBusySlots, workdayStart, workdayEnd); 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
| Aspect | Without Sorting (Brute Force) | Sort First (Optimal) |
|---|---|---|
| Time Complexity | O(n²) — compare every pair | O(n log n) — sort + one linear pass |
| Space Complexity | O(n) result list | O(n) result list (same) |
| Passes Required | Multiple passes over all intervals | Single pass after sorting |
| Correctness Risk | High — easy to miss non-adjacent overlaps | Low — sorted order guarantees adjacency |
| Code Complexity | High — complex nested loop logic | Low — clean, readable single loop |
| Handles Unsorted Input | Yes, but slowly | Yes — sort step handles it explicitly |
| Interview Acceptability | Will fail for n > ~100 in time-limited tests | Standard expected solution |
🎯 Key Takeaways
- Sort by start time first — this single step transforms an O(n²) 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). Use Math.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.
⚠ Common Mistakes to Avoid
- ✕Mistake 1: Using <= instead of < in the overlap check — Symptom: touching intervals like [1,4] and [4,7] are NOT merged, returning [[1,4],[4,7]] instead of [[1,7]] — Fix: use
lastEnd < currentStart(strict less-than) to detect non-overlap. If lastEnd equals currentStart, the intervals touch and should merge, so that condition should be false. - ✕Mistake 2: Forgetting Math.max() when extending the merged interval's end — Symptom: a fully contained interval like [2,5] inside [1,10] shrinks the merged end to 5 instead of keeping it at 10 — Fix: always update the end with
Math.max(existingEnd, currentEnd). Never just assign the current interval's end directly. - ✕Mistake 3: Sorting by end time instead of start time — Symptom: the algorithm produces wrong results on inputs where a long interval starts early but ends late (e.g. [[1,10],[2,3],[4,5]]) because comparisons against the last merged interval's end are no longer reliable — Fix: always sort by start time (index 0). The entire correctness argument of the greedy approach depends on processing intervals in order of their start.
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?
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 doesn't it work to just check if the current interval overlaps with ALL previously merged intervals?
Once you sort by start time, you never need to check earlier intervals. Any interval you process later has a start time >= all previous starts. If the current interval doesn't overlap with 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.
Written and reviewed by senior developers with real-world experience across enterprise, startup and open-source projects. Every article on TheCodeForge is written to be clear, accurate and genuinely useful — not just SEO filler.