1. Introduction

The Merge Intervals pattern is one of the most versatile and frequently used patterns in algorithm design, especially for problems involving ranges, durations, time slots, or segments.
It allows us to efficiently combine overlapping intervals into larger, non-overlapping intervals.

Each interval is typically represented as:

• A pair of numbers [start, end]
• For example, [1, 3] represents an interval starting at 1 and ending at 3.

The goal is to simplify a list of intervals by merging any that overlap or touch.

Let’s see an example before we dive deeper.

Example

Input: [[1,3], [2,6], [8,10], [15,18]]
Output: [[1,6], [8,10], [15,18]]

Explanation:

• Intervals [1,3] and [2,6] overlap because 2 ≤ 3.
• They are merged into [1,6].
• The remaining intervals do not overlap, so they stay as they are.

2. Why This Pattern Matters

This pattern appears everywhere in real-world applications, particularly in systems involving scheduling, memory allocation, time series data, or geometric ranges.

You’ll find it used in:

• Calendar applications (e.g., merging overlapping meeting slots)
• Network systems (e.g., merging IP ranges)
• Operating systems (e.g., merging contiguous free memory blocks)
• Database systems (e.g., merging date ranges in queries)
• Video streaming and logs (e.g., merging playback sessions)
• Geometry and computational graphics (e.g., combining overlapping rectangles projected on one axis)

Thus, mastering this pattern helps you handle a wide range of algorithmic and real-world problems efficiently.

3. When to Use the Merge Intervals Pattern

This pattern should immediately come to mind when:

1. The problem involves ranges or intervals represented by a start and end.
2. You are asked to merge, insert, compare, or detect overlaps between such ranges.
3. The task requires simplifying a list of intervals into a minimal non-overlapping set.

Common problem keywords and hints

When you read any of these phrases in a problem, it’s a strong signal:

• “Overlapping intervals”
• “Merge ranges”
• “Insert interval into schedule”
• “Find free/busy time”
• “Check for meeting conflicts”
• “Combine time slots”

Real-World Analogy

Imagine you’re managing meeting room bookings:

• Meeting 1: 9 AM to 10 AM
• Meeting 2: 9:30 AM to 11 AM
• Meeting 3: 1 PM to 2 PM

Since the first two meetings overlap, you can treat them as a single block of occupied time (9 AM – 11 AM).
This merged view helps visualize the actual busy time in one continuous range.

That’s exactly what the Merge Intervals pattern does — it collapses overlapping ranges into the smallest possible list of continuous intervals.

4. Core Idea

The concept is built on a simple but powerful insight:

If we sort all intervals by their starting time, then overlapping intervals will appear next to each other.

Once sorted, we can traverse the intervals in one linear pass and merge them as we go.

Intuitive Steps

1. Sort intervals by their starting point.
2. Initialize an empty list called merged.
3. For each interval in sorted order:
   • If merged is empty → add the interval.
   • Otherwise, compare the start of the current interval with the end of the last merged interval:
     • If they overlap → merge them.
     • If they don’t overlap → add as a new interval.

5. Visual Understanding

Let’s take the input:

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

After sorting (by start times):

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

Now we visualize on a timeline:

1-----3
   2----------6
                      8----10
                                   15-------18

Merging process:

• [1,3] and [2,6] overlap → merge into [1,6]
• [8,10] and [15,18] don’t overlap → remain separate

Final result:

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

This is a one-pass merging process once sorting is done.

6. Example 1: Merge Overlapping Intervals

Problem

You’re given a list of intervals, each defined by a start and end. Merge all overlapping intervals and return the non-overlapping list.

Input

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

Output

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

7. Step-by-Step Solution

Step 1: Sort by start times

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

After sorting:

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

Step 2: Initialize a result list

merged = []

Step 3: Traverse through intervals

1. Add [1,3] to merged → [[1,3]]
2. Compare next interval [2,6]:
   • It overlaps with [1,3] because 2 <= 3
   • Merge into [1, max(3,6)] = [1,6]
   • Result → [[1,6]]
3. Next interval [8,10] → no overlap → append
   Result → [[1,6],[8,10]]
4. Next [15,18] → no overlap → append
   Result → [[1,6],[8,10],[15,18]]

8. Java Implementation

import java.util.*;

public class MergeIntervals {
    public int[][] merge(int[][] intervals) {
        // Step 1: Sort intervals by start time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

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

        // Step 2: Traverse intervals
        for (int[] interval : intervals) {
            // If merged is empty OR no overlap, add directly
            if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
                merged.add(interval);
            } else {
                // Merge overlapping intervals
                merged.get(merged.size() - 1)[1] = Math.max(
                    merged.get(merged.size() - 1)[1],
                    interval[1]
                );
            }
        }

        // Step 3: Convert list to array
        return merged.toArray(new int[merged.size()][]);
    }
}

Time Complexity

• Sorting → O(N log N)
• Merging → O(N)
• Total = O(N log N)

Space Complexity

• O(N) for the output list

9. Example 2: Insert Interval

Problem

You are given a sorted list of non-overlapping intervals and a new interval.
Insert the new interval and merge if needed.

Input

Intervals = [[1,3],[6,9]], New Interval = [2,5]

Output

[[1,5],[6,9]]

Approach

• Add all intervals that end before new interval starts.
• Merge all that overlap.
• Add all intervals that start after the new interval ends.

Java Code

import java.util.*;

public class InsertInterval {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;

        // Step 1: Add intervals before the new one
        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }

        // Step 2: Merge overlapping intervals
        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.add(newInterval);

        // Step 3: Add remaining intervals
        while (i < intervals.length) {
            result.add(intervals[i]);
            i++;
        }

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

10. Example 3: Meeting Room Conflict Detection

Problem

Given meeting time intervals, determine if a person can attend all meetings.

Input: [[0,30],[5,10],[15,20]]
Output: false

Reasoning

The first two meetings overlap between 5 and 10.

Code

import java.util.*;

public class MeetingRooms {
    public boolean canAttendMeetings(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false; // overlap
            }
        }

        return true;
    }
}

This is the same merging logic, except we stop early if we detect any overlap.

11. Example 4: Employee Free Time

Problem

Given several employees’ work schedules, find all intervals where everyone is free.

Approach

1. Flatten all intervals into one list.
2. Sort by start time.
3. Merge overlapping working intervals.
4. Find gaps between merged intervals — those are the free times.

12. Edge Cases and Mistakes

1. Forgetting to sort – Without sorting, merging logic fails.
2. Touching intervals – Decide if [1,5] and [5,7] count as overlapping.
   • Some problems treat them as merged (<=)
   • Others treat them as separate (<)
3. Empty intervals – Always check if input is empty before processing.
4. Incorrect boundary updates – Always use max() and min() when merging.

13. Complexity Analysis

Operation	Time Complexity	Explanation
Sorting	O(N log N)	Required for arranging by start time
Traversal	O(N)	One pass through all intervals
Total	O(N log N)	Dominated by sorting
Space	O(N)	For merged result list

14. Extensions and Variants

This pattern extends into many related problems:

• Find Intervals Intersection – only keep overlapping portions.
• Count Overlaps – count how many intervals overlap at a time.
• Find Free Time – compute non-overlapping gaps.
• Minimum Meeting Rooms – use heap or sweeping line to track overlaps dynamically.
• Merge k sorted interval lists – used in calendars and timelines.

15. Real-World Applications

Application	Description
Calendar Systems	Combine meeting slots or find free times
Databases	Simplify overlapping validity periods
OS Memory Management	Merge contiguous free memory blocks
Networking	Merge overlapping IP ranges
Event Processing	Combine overlapping event durations

16. Summary of the Pattern

Step	Description
1	Sort intervals by start time
2	Initialize merged list
3	Compare current with previous
4	Merge if overlapping
5	Append otherwise
6	Continue until all are processed

17. Key Takeaways

1. The Merge Intervals pattern simplifies overlapping data ranges efficiently.
2. Always sort first, then merge in one linear scan.
3. Works for time, space, or numerical intervals.
4. Real-world usage includes scheduling, resource management, and log analysis.
5. Time complexity is O(N log N) — dominated by sorting step.