Merge Intervals Pattern

📅 Merge Intervals Animation

[1, 3]👈

[2, 6]

[8, 10]

[15, 18]

05101520

Start: Sort intervals by start time

Step 1 of 6

🎯 Explain Like I'm 5...

Imagine you're coloring on paper 🖍️ and you draw some overlapping lines. When lines touch or overlap, you should merge them into ONE big line!

📏 Your Lines: Line 1 goes from 1 to 4. Line 2 goes from 3 to 6. Line 3 goes from 8 to 10.

🤔 Do they touch?

• Line 1 (1-4) and Line 2 (3-6) OVERLAP! (they share 3-4) → Merge into one line 1-6! ✅
• Line 3 (8-10) doesn't touch the others → Keep it separate! ✅

Result: [1-6] and [8-10] - Just TWO lines instead of three!

🚀 The Trick: First, put your lines in order (1-4, then 3-6, then 8-10). Then go through them and merge any that touch or overlap. It's like combining LEGO pieces that connect! 🧱

When Should You Use This Pattern?

✓Problems involving overlapping intervals
✓Scheduling or calendar problems
✓Finding free time or conflicts
✓Merging time ranges

📝 Example 1: Merge Overlapping Intervals

Given intervals [[1,3], [2,6], [8,10], [15,18]], merge all overlapping intervals.

Step-by-Step Thinking:

Sort intervals by start time: [[1,3], [2,6], [8,10], [15,18]]
Compare [1,3] and [2,6] - they overlap! Merge to [1,6]
Compare [1,6] and [8,10] - no overlap, keep both
Compare [8,10] and [15,18] - no overlap, keep both
Result: [[1,6], [8,10], [15,18]]

MergeIntervals.java

java

import java.util.*;
public class MergeIntervals {
    // Merge all overlapping intervals
    public static int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) {
            return intervals;
        }
        // Step 1: Sort intervals by start time
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        // Step 2: Merge overlapping intervals
        List<int[]> result = new ArrayList<>();
        int[] currentInterval = intervals[0];
        result.add(currentInterval);
        for (int[] interval : intervals) {
            int currentEnd = currentInterval[1];
            int nextStart = interval[0];
            int nextEnd = interval[1];
            // If intervals overlap, merge them
            if (currentEnd >= nextStart) {
                currentInterval[1] = Math.max(currentEnd, nextEnd);
            } else {
                // No overlap, add new interval
                currentInterval = interval;
                result.add(currentInterval);
            }
        }
        return result.toArray(new int[result.size()][]);
    }
    public static void main(String[] args) {
        int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        int[][] merged = merge(intervals);
        System.out.println("Merged intervals:");
        for (int[] interval : merged) {
            System.out.println("[" + interval[0] + ", " + interval[1] + "]");
        }
        // Output: [1, 6], [8, 10], [15, 18]
    }
}

📝 Example 2: Insert Interval

Insert a new interval into sorted non-overlapping intervals and merge if necessary.

InsertInterval.java

java

import java.util.*;
public class InsertInterval {
    public static int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        // Step 1: Add all intervals that come before newInterval
        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }
        // Step 2: Merge all overlapping intervals with newInterval
        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 all remaining intervals
        while (i < intervals.length) {
            result.add(intervals[i]);
            i++;
        }
        return result.toArray(new int[result.size()][]);
    }
    public static void main(String[] args) {
        int[][] intervals = {{1, 3}, {6, 9}};
        int[] newInterval = {2, 5};
        int[][] result = insert(intervals, newInterval);
        System.out.println("After inserting [2, 5]:");
        for (int[] interval : result) {
            System.out.println("[" + interval[0] + ", " + interval[1] + "]");
        }
        // Output: [1, 5], [6, 9]
    }
}

📝 Example 3: Meeting Rooms (Can Attend All?)

Given meeting times, determine if a person can attend all meetings (no overlaps).

MeetingRooms.java

java

import java.util.*;
public class MeetingRooms {
    public static boolean canAttendMeetings(int[][] intervals) {
        // Sort meetings by start time
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        // Check if any two consecutive meetings overlap
        for (int i = 1; i < intervals.length; i++) {
            // If previous meeting ends after current starts = overlap!
            if (intervals[i - 1][1] > intervals[i][0]) {
                return false;  // Cannot attend all meetings
            }
        }
        return true;  // Can attend all meetings!
    }
    public static void main(String[] args) {
        int[][] meetings1 = {{0, 30}, {5, 10}, {15, 20}};
        int[][] meetings2 = {{7, 10}, {2, 4}};
        System.out.println("Can attend meetings1? " + canAttendMeetings(meetings1));
        // Output: false (0-30 overlaps with 5-10 and 15-20)
        System.out.println("Can attend meetings2? " + canAttendMeetings(meetings2));
        // Output: true (2-4 and 7-10 don't overlap)
    }
}

🔑 Key Points to Remember

1️⃣Always sort intervals first (usually by start time)
2️⃣Two intervals [a,b] and [c,d] overlap if b ≥ c
3️⃣Time Complexity: O(n log n) due to sorting
4️⃣Space Complexity: O(n) for the result list

💪 Practice Problems

• Interval List Intersections
• Employee Free Time
• Meeting Rooms II (minimum rooms needed)
• Non-overlapping Intervals
• Minimum Number of Arrows to Burst Balloons