Introduction

The Merge Intervals Pattern is a common coding interview technique used to process overlapping intervals efficiently.

Many scheduling, booking, calendar, networking, and resource allocation problems can be solved using this pattern.

The general approach is:

1. Sort intervals by their start time.
2. Compare consecutive intervals.
3. Merge overlapping intervals.
4. Produce a new list of non-overlapping intervals.

---

When Should You Use Merge Intervals?

Use this pattern when the problem involves:

• Time ranges
• Date ranges
• Meeting schedules
• Reservations
• Resource allocation
• Booking systems
• Overlapping intervals
• Calendar events

Common interview keywords:

• Merge
• Overlap
• Intervals
• Meeting Rooms
• Calendar
• Schedule
• Free Time

---

Problem Example

Input

[[1,3],[2,6],[8,10],[15,18]]

Output

[[1,6],[8,10],[15,18]]

Explanation

graph TD
    N_1_3["1------3"] --> N_2_6["2---------6"]
    N_2_6["2---------6"] --> Merge["Merge"]
    Merge["Merge"] --> N_1_6["1------------6"]

---

Visualization

Before Merge

1-----3

   2-------6

              8---10

                     15----18

After Merge

1------------6

              8---10

                     15----18

---

Core Idea

After sorting,

only compare the current interval with the previous merged interval.

If

Current Start

<=

Previous End

Merge them.

Otherwise,

store the previous interval and start a new one.

---

Algorithm

graph TD
    Sort_intervals["Sort intervals"] --> Initialize_merged_list["Initialize merged list"]
    Initialize_merged_list["Initialize merged list"] --> For_every_interval["For every interval"]
    For_every_interval["For every interval"] --> Overlap["Overlap?"]
    Overlap["Overlap?"] --> Yes["Yes"]
    Yes["Yes"] --> Update_End["Update End"]
    Update_End["Update End"] --> No["No"]
    No["No"] --> Add_Previous["Add Previous"]
    Add_Previous["Add Previous"] --> Continue["Continue"]
    Continue["Continue"] --> Return_merged_intervals["Return merged intervals"]

---

Step-by-Step Dry Run

Input

[[1,3],[2,6],[8,10],[15,18]]

Start

Merged

[1,3]

Compare

[2,6]

Since

2 <= 3

Merge

[1,6]

Next

[8,10]

No overlap

Store

[1,6]

Continue

Merged

[8,10]

Next

[15,18]

No overlap

Final Answer

[[1,6],[8,10],[15,18]]

---

Java Solution

import java.util.*;

public class MergeIntervals {

    public static int[][] merge(int[][] intervals) {

        Arrays.sort(intervals,
                Comparator.comparingInt(a -> a[0]));

        List<int[]> result = new ArrayList<>();

        int[] current = intervals[0];

        for (int i = 1; i < intervals.length; i++) {

            if (intervals[i][0] <= current[1]) {

                current[1] = Math.max(
                        current[1],
                        intervals[i][1]);

            } else {

                result.add(current);

                current = intervals[i];

            }

        }

        result.add(current);

        return result.toArray(new int[result.size()][]);

    }

    public static void main(String[] args) {

        int[][] intervals = {
                {1,3},
                {2,6},
                {8,10},
                {15,18}
        };

        int[][] answer = merge(intervals);

        for (int[] interval : answer) {

            System.out.println(
                    interval[0] + " " + interval[1]);

        }

    }

}

---

Internal Working

Sorted

1 3

2 6

8 10

15 18

Processing

graph TD
    Current["Current"] --> N_1_3["1 3"]
    N_1_3["1 3"] --> Overlap["Overlap"]
    Overlap["Overlap"] --> N_1_6["1 6"]
    N_1_6["1 6"] --> Store["Store"]
    Store["Store"] --> N_8_10["8 10"]
    N_8_10["8 10"] --> Store["Store"]
    Store["Store"] --> N_15_18["15 18"]

---

Complexity Analysis

Operation	Complexity
Sorting	O(n log n)
Merge Traversal	O(n)
Total Time	O(n log n)
Extra Space	O(n)

Sorting dominates the overall complexity.

---

Why Sorting is Required

Without sorting

[8,10]

[1,3]

[2,6]

Intervals cannot be merged correctly because overlaps are not processed in order.

Sorting guarantees that every interval is compared with the correct previous interval.

---

Production Use Cases

Google Calendar

Merge overlapping meetings.

---

Microsoft Outlook

Combine continuous appointments.

---

Airline Reservation Systems

Merge overlapping seat reservations.

---

Hotel Booking Platforms

Handle overlapping room reservations.

---

CPU Scheduling

Merge adjacent execution windows.

---

Network Firewalls

Merge overlapping IP address ranges.

---

Cloud Resource Allocation

Merge overlapping VM reservation windows.

---

Healthcare Systems

Combine overlapping patient appointment slots.

---

Common Merge Interval Problems

Problem	Difficulty
Merge Intervals	Medium
Insert Interval	Medium
Meeting Rooms	Easy
Meeting Rooms II	Medium
Employee Free Time	Hard
Interval List Intersections	Medium
Non-overlapping Intervals	Medium
Minimum Number of Arrows	Medium

---

Common Mistakes

Forgetting to Sort

This is the most common mistake.

Always sort first.

---

Wrong Overlap Condition

Correct

currentStart <= previousEnd

Incorrect

currentStart < previousEnd

which fails when intervals touch.

---

Forgetting Final Interval

After the loop,

always add the last merged interval.

---

Updating the Wrong End Value

Always use

Math.max(currentEnd, nextEnd)

---

Ignoring Empty Input

Handle

intervals.length == 0

before accessing the first interval.

---

Interview Tips

Mention these observations:

• Sorting is mandatory.
• After sorting, only adjacent intervals need comparison.
• Each interval is processed exactly once after sorting.
• Time complexity is dominated by sorting.

---

Frequently Asked Interview Questions

1. What is the Merge Intervals pattern?

Answer

It is a pattern used to combine overlapping intervals into a minimal set of non-overlapping intervals after sorting them by start time.

---

2. Why is sorting required?

Answer

Sorting ensures overlapping intervals appear next to each other, making it possible to merge them in a single traversal.

---

3. What is the time complexity?

Answer

O(n log n) because sorting takes O(n log n) and merging takes O(n).

---

4. What is the space complexity?

Answer

Typically O(n) for storing the merged intervals.

---

5. How do you determine whether two intervals overlap?

Answer

Two intervals overlap if the start of the current interval is less than or equal to the end of the previous merged interval.

---

6. Why use Math.max() while merging?

Answer

The merged interval should end at the larger of the two end values to cover the complete overlapping range.

---

7. Which problems commonly use this pattern?

Answer

Merge Intervals, Insert Interval, Meeting Rooms, Employee Free Time, Interval List Intersections, and Non-overlapping Intervals.

---

8. Where is this pattern used in production?

Answer

Calendar applications, reservation systems, cloud scheduling, networking, operating systems, healthcare scheduling, and financial systems.

---

9. What is the biggest mistake candidates make?

Answer

Forgetting to sort the intervals before attempting to merge them.

---

10. Can Merge Intervals be solved without sorting?

Answer

Generally, no. Without sorting, identifying all overlapping intervals efficiently becomes difficult, leading to more complex or less efficient solutions.

---

Quick Revision

Topic	Summary
Pattern	Merge Intervals
First Step	Sort by Start Time
Processing	Single Pass
Time Complexity	O(n log n)
Space Complexity	O(n)
Main Condition	currentStart <= previousEnd
Interview Frequency	⭐⭐⭐⭐⭐

---

Key Takeaways

• Merge Intervals is one of the most common interval-based coding interview patterns.
• Always sort intervals before processing.
• Compare only adjacent intervals after sorting.
• Merge overlapping intervals by updating the end value with Math.max().
• This pattern is heavily used in scheduling, booking, networking, cloud computing, and calendar systems.

---