Intermediate 4 min · March 05, 2026

Merge Intervals — Sort-by-End Breaks Greedy Invariant

Sort-by-end broke the greedy invariant: [1,10],[2,3],[4,5] merged to [2,3],[4,10] instead of [1,10].

N
Naren · Founder
Plain-English first. Then code. Then the interview question.
About
 ● Production Incident 🔎 Debug Guide
⚡Quick Answer
  • 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.
Plain-English First

Imagine you're booking meeting rooms for a busy office. Several meetings overlap — one runs 9-11am and another 10am-12pm, so you can just block off 9am-12pm as one big chunk. The merge intervals problem is exactly this: given a list of time slots (or any numeric ranges), collapse all the overlapping ones into the smallest set of non-overlapping blocks. It's the algorithm behind your calendar app when it shows you a clean schedule instead of a jumbled mess.

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]].

  1. Sort by start time: already sorted → [[1,3],[2,6],[8,10],[15,18]].
  2. merged = [[1,3]]. Compare [2,6]: start=2 <= last_end=3, so merge → update last to [1,6].
  3. Compare [8,10]: start=8 > last_end=6, no overlap → append [8,10]. merged=[[1,6],[8,10]].
  4. Compare [15,18]: start=15 > last_end=10, no overlap → append. merged=[[1,6],[8,10],[15,18]].
  5. 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]].

io/thecodeforge/algo/WorkedExampleMergeIntervals.javaJAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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)));
    }
}
Output
Input: [[1, 3], [2, 6], [8, 10], [15, 18]]
Merged: [[1, 6], [8, 10], [15, 18]]
The Two Building Blocks
  • 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.
Production Insight
A resource allocator merged overlapping CPU time slices to detect scheduling conflicts. With 50,000 time slices per second, the O(n log n) sort + O(n) merge processed all slices in 2ms. The naive O(n^2) pairwise comparison would have taken 2.5 seconds — too slow for real-time scheduling. The sort-then-merge approach enabled conflict detection within the 5ms scheduling quantum.
Key Takeaway
Sort by start time, then merge in a single pass. The sort is mandatory — without it, the single-pass approach misses non-adjacent overlaps. The merge is a one-line check: if currentStart <= lastEnd, extend with max(lastEnd, currentEnd).

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]].

io/thecodeforge/algo/MergeIntervalsAlgorithm.javaJAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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}})));
    }
}
Output
Merged: [[1, 6], [8, 10], [15, 18]]
Empty: []
Single: [[3, 7]]
Touching: [[1, 7]]
Contained: [[1, 10]]
Pro Tip: Use Integer.compare for Overflow-Safe Sorting
  • 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.
Production Insight
A financial trading system merged overlapping order book price ranges to detect arbitrage opportunities. The sort comparator used a[0] - b[0]. On a day when a price was Integer.MIN_VALUE (representing a canceled order with sentinel value), the subtraction overflowed, producing wrong sort order. The merge then produced incorrect consolidated ranges, and the arbitrage detector fired false positives. The fix: switch to Integer.compare(a[0], b[0]). The team added a lint rule to flag all subtraction-based comparators.
Key Takeaway
The algorithm is sort-then-merge: O(n log n) sort, O(n) merge pass. The non-overlap condition is lastEnd < currentStart (strict). The merge uses Math.max — never direct assignment. Use Integer.compare for overflow-safe sorting.

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.

io/thecodeforge/algo/MergeIntervals.javaJAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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)));
    }
}
Output
Merged: [[1, 6], [8, 10], [15, 18]]
Interview Gold: Why Sort-Then-Merge Is Correct
  • 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.
Production Insight
A database query optimizer merged overlapping index range scans to avoid reading the same disk block twice. Without sort-then-merge, the optimizer compared every pair of range scans: O(n^2) on 10,000 range scans = 100 million comparisons. With sort-then-merge: O(n log n) sort + O(n) merge = 133,000 operations. The 750x speedup enabled real-time query optimization during the planning phase, which had a 10ms budget.
Key Takeaway
Sorting by start time is the entire secret. It transforms O(n^2) pairwise comparison into O(n) sequential comparison. The greedy proof: if current.start > lastMerged.end, no earlier interval can overlap. This transitive property only holds with start-time ordering.

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.

io/thecodeforge/algo/MergeIntervalsEdgeCases.javaJAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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}}));
    }
}
Output
Touching [1,4],[4,7]: [1,7]
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]
Watch Out: Defensive Copies in Production Code
  • mergedList.add(currentInterval): stores reference to original array. Caller mutation corrupts result.
  • mergedList.add(new int[]{start, end}): stores defensive copy. Caller mutation does not affect result.
  • Test: modify input after merge, check if result changes. If it does, defensive copy is missing.
  • In production: always use defensive copies. In interviews: mention it to signal production awareness.
  • This applies to any function that stores references to mutable input objects.
Production Insight
A firewall rule engine merged overlapping CIDR blocks to reduce the number of rules evaluated per packet. The merge function stored references to the original rule arrays. When the rule engine later modified a rule's priority (changing the array contents), the merged result was silently corrupted. The firewall evaluated wrong rules for 3 hours before the bug was detected. The fix: use defensive copies. The team added a lint rule to flag all .add(inputArray) calls in merge functions.
Key Takeaway
Edge cases win interviews: touching intervals (use strict <), contained intervals (use Math.max), empty/single input (guard clause), no-overlap input (all added independently). In production, always use defensive copies — never store references to mutable input arrays.

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).

io/thecodeforge/algo/CalendarFreeSlotFinder.javaJAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
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");
        }
    }
}
Output
Alex's free slots today:
11:00 - 13:00
15:00 - 16:00
Interview Gold: The Problem Composes with Itself
  • 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.
Production Insight
A meeting scheduling service found common free time for 5-person teams. The naive approach: enumerate all possible time slots and check each person's availability. With 96 fifteen-minute slots per day and 5 people, that is 96 x 5 = 480 checks per day. The interval approach: merge each person's busy slots (5 x O(n log n)), find free slots (5 x O(n)), intersect all free-slot lists (4 pairwise intersections). Total: O(5n log n + 5n + 4n) = O(n log n). The service found common slots in 0.3ms vs 12ms for the naive approach — a 40x speedup.
Key Takeaway
Merge intervals shows up in calendar systems, database optimizers, firewalls, and video editors. The free-slot finder is the natural inverse: merge busy blocks, gaps are free time. The pattern composes with itself — common free time is the intersection of two free-slot lists.
● Production incidentPOST-MORTEMseverity: high

Calendar Service Double-Booked Users: Sorted by End Time Instead of Start Time

Symptom
Calendar service showed available slots during times that were actually booked. 23% of users received double-bookings because the conflict detection returned incomplete merged intervals. The free-slot finder showed gaps inside the all-day meeting [1,10] because the merge produced [2,3], [4,10] instead of [1,10].
Assumption
A timezone conversion bug caused interval boundaries to shift, creating phantom gaps. The team spent 5 hours checking timezone handling, DST transitions, and UTC conversion logic.
Root cause
The merge function sorted by end time (index 1) instead of start time (index 0): Arrays.sort(intervals, (a, b) -> a[1] - b[1]). With sort-by-end, the processing order was [2,3], [4,5], [1,10]. The algorithm compared each interval only against the last merged interval. [1,10] was compared against [4,5] (the last merged), found overlap, and merged to [4,10]. But [1,10] also overlapped [2,3], which was already committed to the result list. The sort-by-end order broke the greedy invariant: 'if the current interval doesn't overlap the last merged interval, it doesn't overlap any earlier one.' This invariant only holds with sort-by-start.
Fix
1. Changed the sort comparator from a[1] - b[1] to Integer.compare(a[0], b[0]). Now intervals are processed in start-time order. 2. Added a unit test: merge [[1,10],[2,3],[4,5]] must return [[1,10]]. With sort-by-end, this returned [[2,3],[4,10]]. 3. Added a validation: after merge, verify no output interval overlaps another. If any pair overlaps, flag as merge invariant violation. 4. Added a comment: 'ALWAYS sort by start time (index 0). Sort-by-end breaks the greedy invariant. See incident #6291.' 5. Added a metric: merge_intervals_sort_order_violation_total to catch future regressions.
Key lesson
  • Sort by start time, never by end time. The greedy single-pass approach only works with start-time ordering.
  • The merge invariant is: 'if current interval doesn't overlap the last merged interval, it doesn't overlap any earlier one.' This only holds with sort-by-start.
  • Test with a long interval followed by short contained intervals: [[1,10],[2,3],[4,5]]. Expected: [[1,10]].
  • Add post-merge validation: verify no output interval overlaps another. This catches sort-order bugs.
  • Document the sort requirement in code comments. Future developers will not know why start-time sorting is mandatory.
Production debug guideSymptom-first investigation path for interval merging bugs.6 entries
Symptom · 01
Merged result contains overlapping intervals (e.g., [[1,5],[3,8]] instead of [[1,8]]).
→
Fix
Check if the input is sorted by start time. Without sorting, the single-pass merge misses non-adjacent overlaps. Add Arrays.sort(intervals, Comparator.comparingInt(a -> a[0])).
Symptom · 02
Touching intervals like [1,4] and [4,7] are not merged.
→
Fix
Check the non-overlap condition. If using lastEnd <= currentStart, touching intervals are treated as non-overlapping. Change to lastEnd < currentStart (strict less-than).
Symptom · 03
Contained interval [2,5] inside [1,10] shrinks the merged end to 5.
→
Fix
Check if the merge uses Math.max(lastEnd, currentEnd). If it assigns currentEnd directly, contained intervals shrink the result. Change to lastEnd = Math.max(lastEnd, currentEnd).
Symptom · 04
ArrayIndexOutOfBoundsException on empty input.
→
Fix
Add a null/empty guard: if (intervals == null || intervals.length == 0) return new int[0][0]. Without it, accessing intervals[0] crashes on empty arrays.
Symptom · 05
Merged result is corrupted after the caller modifies the input array.
→
Fix
Check if the result stores references to the original input arrays. Use new int[]{start, end} for defensive copies instead of adding the original interval reference.
Symptom · 06
Integer overflow in the sort comparator (a[0] - b[0]).
→
Fix
Replace a[0] - b[0] with Integer.compare(a[0], b[0]). The subtraction overflows when interval values are near Integer.MIN_VALUE or MAX_VALUE.
★ Merge Intervals TriageRapid checks to isolate interval merging bugs.
Merged result contains overlapping intervals.−
Immediate action
Check if input is sorted by start time.
Commands
Print sort order: System.out.println(Arrays.deepToString(intervals)) — verify intervals are sorted by index 0
Test with unsorted input [[3,4],[1,2],[5,6]] — expected [[1,2],[3,4],[5,6]]
Fix now
Add Arrays.sort(intervals, Comparator.comparingInt(a -> a[0])) before the merge loop.
Touching intervals not merged ([1,4],[4,7] stays as two intervals).+
Immediate action
Check non-overlap condition: < vs <=.
Commands
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 <
Fix now
Change non-overlap check to lastEnd < currentStart (strict less-than).
Contained interval shrinks merged end ([1,10] + [2,5] → [1,5] instead of [1,10]).+
Immediate action
Check if merge uses Math.max or direct assignment.
Commands
Test with [[1,10],[2,5]] — expected [[1,10]]
If result is [[1,5]], the merge assigns currentEnd instead of max(lastEnd, currentEnd)
Fix now
Change merge to lastEnd = Math.max(lastEnd, currentEnd).
Result is corrupted after caller modifies input.+
Immediate action
Check if result stores original interval references.
Commands
Print identity: System.out.println(result[0] == intervals[0]) — if true, same reference
Modify input after merge and check if result changes
Fix now
Use new int[]{start, end} when adding to result list. Never add the original interval reference.
Merge Intervals Approaches Compared
AspectWithout Sorting (Brute Force)Sort First (Optimal)Sort by End Time (Wrong)
Time ComplexityO(n^2) — compare every pairO(n log n) — sort + one linear passO(n log n) — sort + one linear pass
Space ComplexityO(n) result listO(n) result listO(n) result list
Passes RequiredMultiple passes over all intervalsSingle pass after sortingSingle pass after sorting
Correctness RiskHigh — easy to miss non-adjacent overlapsLow — sorted order guarantees adjacencyHigh — greedy invariant broken
Code ComplexityHigh — complex nested loop logicLow — clean, readable single loopLow — looks correct but produces wrong results
Handles Unsorted InputYes, but slowlyYes — sort step handles it explicitlyYes — but produces wrong merged intervals
Interview AcceptabilityWill fail for n > ~100 in time-limited testsStandard expected solutionWill be rejected — sort by start, not end
Greedy InvariantN/A — no invariantcurrent.start > lastMerged.end implies no earlier overlapBroken — lastMerged.end is not >= all earlier ends

Key takeaways

1
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.
2
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.
3
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.
4
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.
5
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.
6
Use Integer.compare or Comparator.comparingInt for overflow-safe sorting. Subtraction-based comparators overflow on extreme values.
7
Test with
touching intervals [1,4],[4,7], contained interval [1,10],[2,5], empty input, single interval, and no-overlap input.
8
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.
INTERVIEW PREP · PRACTICE MODE

Interview Questions on This Topic

FAQ · 8 QUESTIONS

Frequently Asked Questions

01
What is the time complexity of the merge intervals algorithm?
02
Should touching intervals like [1,4] and [4,7] be merged into [1,7]?
03
Why with ALL previously merged intervals?
04
What if intervals are not sorted?
05
How do you find the insertion position of a new interval into sorted non-overlapping intervals?
06
Why do we sort by start time before merging?
07
How do we handle the case where one interval completely contains another?
08
What happens if you sort by end time instead of start time?
Related Next Steps
→Interval Scheduling Maximization — Selecting the Maximum Non-Overlapping SubsetThe greedy activity selection problem: sort by end time, select non-overlapping intervals greedily. Related but different from merge intervals.
🔥

That's Arrays & Strings. Mark it forged?

4 min read · try the examples if you haven't

←
Previous
Rotate Array Problem
11 / 13 · Arrays & Strings
Next
Next Permutation Algorithm
→