medium Merge Intervals

Problem Statement

Given a list of intervals, merge all the overlapping intervals to produce a list that has only mutually exclusive intervals.

Example 1:

Intervals: [[1,4], [2,5], [7,9]]
Output: [[1,5], [7,9]]
Explanation: Since the first two intervals [1,4] and [2,5] overlap, we merged them into one [1,5].

Example 2:

Intervals: [[6,7], [2,4], [5,9]]
Output: [[2,4], [5,9]]
Explanation: Since the intervals [6,7] and [5,9] overlap, we merged them into one [5,9].

Example 3:

Intervals: [[1,4], [2,6], [3,5]]
Output: [[1,6]]
Explanation: Since all the given intervals overlap, we merged them into one.

Constraints:

1 <= intervals.length <= 10⁴
intervals[i].length == 2
0 <= start_i <= end_i <= 10⁴

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Merge Intervals medium

0. Pattern family

Family: Sort + linear merge

1. Why / judgment (K3)

Sort by start; scan merging if cur.start ≤ last.end else append. Overlaps and touches depend on inclusive ends.

2. Worked complexity / derivation (K11)

O(n log n) sort + O(n) merge; space O(n) output.

3. Pattern + recognition + when-NOT (K12)

Name: INTERVAL MERGE

Recognition: merge overlapping intervals; free time; meeting rooms related.

When-NOT: Insert one interval into sorted list → O(n) without full sort. Interval graph coloring → meeting rooms II heap.

4. Edge hand-run (K13)

[] → []. Single. Nested [1,4][2,3]→[1,4]. Touching [1,2][2,3]→[1,3] if closed.

5. Interviewer follow-ups & drills

Q1. Sort by end?
Model answer: Start sort is standard for merge.

Q2. In-place?
Model answer: Possible with write index after sort.

Q3. Open intervals?
Model answer: Touching may not merge — define predicates.

✅ Solution Merge Intervals

Problem Statement

Given a list of intervals, merge all the overlapping intervals to produce a list that has only mutually exclusive intervals.

Example 1:

Intervals: [[1,4], [2,5], [7,9]]
Output: [[1,5], [7,9]]
Explanation: Since the first two intervals [1,4] and [2,5] overlap, we merged them into one [1,5].

Example 2:

Intervals: [[6,7], [2,4], [5,9]]
Output: [[2,4], [5,9]]
Explanation: Since the intervals [6,7] and [5,9] overlap, we merged them into one [5,9].

Example 3:

Intervals: [[1,4], [2,6], [3,5]]
Output: [[1,6]]
Explanation: Since all the given intervals overlap, we merged them into one.

Constraints:

1 <= intervals.length <= 10⁴
intervals[i].length == 2
0 <= start_i <= end_i <= 10⁴

Solution

Let’s take the example of two intervals (‘a’ and ‘b’) such that a.start <= b.start. There are four possible scenarios:

Our goal is to merge the intervals whenever they overlap. For the above-mentioned three overlapping scenarios (2, 3, and 4), this is how we will merge them:

To solve this problem, we will sort the list of intervals by their start times. This helps in easily identifying overlapping intervals. After sorting, we can iterate through the intervals, merging them if they overlap. We will maintain a list to store the merged intervals. As we iterate, we compare the current interval with the last interval in the merged list. If they overlap, we merge them by extending the end time. Otherwise, we add the current interval to the merged list.

This approach works because sorting brings overlapping intervals next to each other. This allows us to handle overlapping intervals in a single pass through the list. Sorting the intervals first is key to simplifying the merging process.

Step-by-Step Algorithm

Sort Intervals:
- Begin by sorting the list of intervals based on their start times.
- This can be done using a comparator in Java.
Initialize Merged List:
- Create an empty list called mergedIntervals to store the merged intervals.
Set Initial Interval:
- Start by picking the first interval and set it as the current interval.
Iterate Through Intervals:
- Loop through the rest of the intervals.
- For each interval:
  - Check Overlap:
    - If the start of the current interval is less than or equal to the end of the previous interval, it means they overlap.
    - In this case, merge them by updating the end of the previous interval to be the maximum of both ends.
  - Non-overlapping:
    - If they do not overlap, add the previous interval to the mergedIntervals list.
    - Update the current interval to be the next interval in the list.
Add Last Interval:
- After the loop completes, add the last interval to the mergedIntervals list.
Return Result:
- Return the mergedIntervals list as the final output.

Algorithm Walkthrough

Given input: [[1, 4], [2, 5], [7, 9]]

Sort Intervals:
- Original intervals: [[1, 4], [2, 5], [7, 9]]
- Sorted intervals: [[1, 4], [2, 5], [7, 9]] (already sorted)
Initialize Merged List:
- mergedIntervals: []
Set Initial Interval:
- Current interval: [1, 4]
Iterate Through Intervals:
- First Iteration:
  - Next interval: [2, 5]
  - Check overlap: 2 <= 4 (True)
  - Merge intervals: [1, 5]
  - Update current interval: [1, 5]
- Second Iteration:
  - Next interval: [7, 9]
  - Check overlap: 7 <= 5 (False)
  - Add previous interval to mergedIntervals: [[1, 5]]
  - Update current interval: [7, 9]
Add Last Interval:
- Add last interval to mergedIntervals: [[1, 5], [7, 9]]
Return Result:
- mergedIntervals: [[1, 5], [7, 9]]

Code

Here is what our algorithm will look like:

java

import java.util.*;

/*class Interval {
  int start;
  int end;

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

class Solution {

  public List<Interval> merge(List<Interval> intervals) {
    if (intervals.size() < 2) return intervals;

    // sort the intervals by start time
    Collections.sort(intervals, (a, b) -> Integer.compare(a.start, b.start));

    List<Interval> mergedIntervals = new LinkedList<Interval>();
    Iterator<Interval> intervalItr = intervals.iterator();
    Interval interval = intervalItr.next();
    int start = interval.start;
    int end = interval.end;

    while (intervalItr.hasNext()) {
      interval = intervalItr.next();
      if (interval.start <= end) { // overlapping intervals, adjust the 'end'
        end = Math.max(interval.end, end);
      } else { // non-overlapping interval, add the previous interval and reset
        mergedIntervals.add(new Interval(start, end));
        start = interval.start;
        end = interval.end;
      }
    }
    // add the last interval
    mergedIntervals.add(new Interval(start, end));

    return mergedIntervals;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    List<Interval> input = new ArrayList<Interval>();
    input.add(new Interval(1, 4));
    input.add(new Interval(2, 5));
    input.add(new Interval(7, 9));
    System.out.print("Merged intervals: ");
    for (Interval interval : sol.merge(input)) System.out.print(
      "[" + interval.start + "," + interval.end + "] "
    );
    System.out.println();

    input = new ArrayList<Interval>();
    input.add(new Interval(6, 7));
    input.add(new Interval(2, 4));
    input.add(new Interval(5, 9));
    System.out.print("Merged intervals: ");
    for (Interval interval : sol.merge(input)) System.out.print(
      "[" + interval.start + "," + interval.end + "] "
    );
    System.out.println();

    input = new ArrayList<Interval>();
    input.add(new Interval(1, 4));
    input.add(new Interval(2, 6));
    input.add(new Interval(3, 5));
    System.out.print("Merged intervals: ");
    for (Interval interval : sol.merge(input)) System.out.print(
      "[" + interval.start + "," + interval.end + "] "
    );
    System.out.println();
  }
}

Time Complexity

The time complexity of the above algorithm is , where ‘N’ is the total number of intervals. We are iterating the intervals only once which will take O(N), in the beginning though, since we need to sort the intervals, our algorithm will take .

Space Complexity

The space complexity of the above algorithm will be O(N) as we need to return a list containing all the merged intervals. We will also need O(N) space for sorting. For Java, depending on its version, Collections.sort() either uses Merge sort or Timsort, and both these algorithms need O(N) space. Overall, our algorithm has a space complexity of O(N).

🎯 STRICT STANDOUT — Solution Merge Intervals

0. Pattern family

Family: Sort + merge scan

1. Why / judgment (K3)

Sort starts; maintain current merged; extend end with max; push when disjoint.

2. Worked complexity / derivation (K11)

O(n log n).

3. Pattern + recognition + when-NOT (K12)

Name: INTERVAL MERGE

Recognition: merge overlaps after sort.

When-NOT: Online unsorted stream without buffering all.

4. Edge hand-run (K13)

All overlap one; all disjoint; reverse-sorted input needs sort.

5. Interviewer follow-ups & drills

Q1. Key = start?
Model answer: Yes.

Q2. Mutable last?
Model answer: merged[-1][1]=max(...)

Q3. Meeting rooms link?
Model answer: Same sort start; heap of ends for room count.

🧩 Pattern · Intervals

Recognize it: Overlapping ranges → sort by start, then sweep and merge.

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Merge Intervals? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Merge Intervals** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Merge Intervals** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Merge Intervals**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Merge Intervals**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Count Unreachable Pairs of Nodes i Delete Node in a BST →

medium Merge Intervals

Problem Statement

Try it yourself

🎯 STRICT STANDOUT — Merge Intervals medium

0. Pattern family

1. Why / judgment (K3)

2. Worked complexity / derivation (K11)

3. Pattern + recognition + when-NOT (K12)

4. Edge hand-run (K13)

5. Interviewer follow-ups & drills

Problem Statement

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Similar Problems

🎯 STRICT STANDOUT — Solution Merge Intervals

0. Pattern family

1. Why / judgment (K3)

2. Worked complexity / derivation (K11)

3. Pattern + recognition + when-NOT (K12)

4. Edge hand-run (K13)

5. Interviewer follow-ups & drills

📝 My notes