Mastering Merge Intervals: A Crucial Algorithm Technique

Merge Intervals is a common algorithmic pattern used to solve problems involving overlapping or sortable ranges. Understanding this pattern significantly improves your problem-solving skills. This technique involves merging overlapping intervals into a set of non-overlapping intervals.

Understanding Merge Intervals

Imagine you have a list of time intervals, each represented by a start and end time. Merge Intervals aims to combine overlapping intervals into a single, larger interval. For instance:

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

After merging, this becomes:

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

Because [1, 3] and [2, 6] overlap, they're combined into [1, 6].


flowchart TD
    subgraph Timeline["Interval Overlap Evaluation (Sorted by Start Time)"]
        direction TB
        A["Interval A: [1 ------------ 3]"]
        B["Interval B:     [2 ------------ 6] (Overlaps A: 2 <= 3)"]
        C["Interval C:                 [8 ---- 10] (No Overlap: 8 > 6)"]
    end
    Timeline --> Decision{"next.start <= current.end ?"}
    Decision -- Yes --> Merge["Merge Overlapping:
current.end = max(current.end, next.end)
Result: [1 ---------------- 6]"]
    Decision -- No --> Commit["No Overlap:
Add current to results
current = next"]

Identifying the Merge Intervals Pattern

How do you spot this pattern in a problem? Look for these common indicators:

Intervals: The problem explicitly involves ranges or intervals, often defined by start and end points (e.g., time periods, coordinates, etc.).
Overlapping or adjacent ranges: The problem description suggests or implies that some ranges might overlap or be adjacent.
Merging or consolidation: The goal is to combine or simplify the set of ranges. The output often expects a smaller, non-overlapping set.
Sorting: Sorting the intervals by their start times is almost always a necessary preprocessing step.

Example Problem: Meeting Rooms

Given an array of meeting time intervals [[start, end]], determine if a person can attend all meetings. This directly involves checking for overlapping intervals.

How to Check for Merge Intervals in a Question

Consider a question that asks about overlapping intervals. Questions like "find the minimum number of meeting rooms needed" or "determine if all given intervals can be scheduled without overlap" strongly hint at a Merge Intervals solution. Examine the inputs: if they are ranges or intervals, then Merge Intervals is likely applicable.

Implementation Examples

Java:

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

class Interval {
    int start;
    int end;

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

public class MergeIntervals {
    public static List<Interval> merge(Interval[] intervals) {
        if (intervals.length <= 1) return Arrays.asList(intervals);
        Arrays.sort(intervals, (a, b) -> Integer.compare(a.start, b.start));
        List<Interval> result = new ArrayList<>();
        Interval current = intervals[0];
        for (int i = 1; i < intervals.length; i++) {
            Interval next = intervals[i];
            if (next.start <= current.end) {
                current.end = Math.max(current.end, next.end);
            } else {
                result.add(current);
                current = next;
            }
        }
        result.add(current);
        return result;
    }

    public static void main(String[] args) {
        Interval[] intervals = {new Interval(1, 3), new Interval(2, 6), new Interval(8, 10), new Interval(15, 18)};
        List<Interval> merged = merge(intervals);
        for (Interval interval : merged) {
            System.out.println("[" + interval.start + ", " + interval.end + "]");
        }
    }
}

Python:

intervals = [[1,3],[2,6],[8,10],[15,18]]
intervals.sort()
merged = []
current_interval = intervals[0]
for next_interval in intervals[1:]:
    if next_interval[0] <= current_interval[1]:
        current_interval[1] = max(current_interval[1], next_interval[1])
    else:
        merged.append(current_interval)
        current_interval = next_interval
merged.append(current_interval)
print(merged)

JavaScript:

function mergeIntervals(intervals) {
  if (intervals.length <= 1) return intervals;
  intervals.sort((a, b) => a[0] - b[0]);
  let merged = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    let current = merged[merged.length - 1];
    let next = intervals[i];
    if (next[0] <= current[1]) {
      merged[merged.length - 1][1] = Math.max(current[1], next[1]);
    } else {
      merged.push(next);
    }
  }
  return merged;
}

let intervals = [[1,3],[2,6],[8,10],[15,18]];
console.log(mergeIntervals(intervals));

Tips and Tricks

Always sort the intervals: Sorting by start time is crucial for efficient merging.
Use a current interval: Keep track of the currently merged interval to avoid redundant comparisons.
Consider edge cases: Handle empty input arrays or arrays with a single interval.

Mastering Algorithms: A Deep Dive into Merge Intervals

This blog post explores the Merge Intervals algorithm, a fundamental technique in computer science with broad applications. We'll dissect the problem, walk through a step-by-step solution, provide multiple examples, and offer code implementations in Java, Python, and JavaScript.

Understanding Merge Intervals

The Merge Intervals problem involves taking a collection of intervals (represented as pairs of start and end times) and merging overlapping intervals into a single, consolidated interval. For example, if you have intervals [1, 3], [2, 6], and [8, 10], merging them results in [1, 6] and [8, 10] because [1, 3] and [2, 6] overlap.

Step-by-Step Solution: Identifying the Pattern and Solving the Problem

Sort: The key to efficiently merging intervals is to first sort them based on their start times. This allows us to easily identify overlapping intervals.
Iterate and Merge: Iterate through the sorted intervals. Compare the current interval's start time with the previous interval's end time. If the current interval's start time is less than or equal to the previous interval's end time, they overlap. Merge them by creating a new interval with the minimum start time (from both) and the maximum end time (from both). If they don't overlap, add the current interval to the result list.
Result: The final result list will contain the merged intervals.

Example: Merge Intervals in Action

Let's consider the intervals [[1,3],[2,6],[8,10],[15,18]].

Sort: The intervals are already sorted by start time.
Iterate and Merge:
- [1,3] and [2,6] overlap (3 >= 2). Merge to get [1,6].
- [1,6] and [8,10] do not overlap.
- [8,10] and [15,18] do not overlap.
Result: The merged intervals are [[1, 6], [8, 10], [15, 18]].

Code Implementations

Java:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

class Interval {
    int start;
    int end;
    Interval(int s, int e) { start = s; end = e; }
}

public class MergeIntervals {
    public List<Interval> merge(Interval[] intervals) {
        if (intervals.length <= 1) return Arrays.asList(intervals);
        Arrays.sort(intervals, Comparator.comparingInt(a -> a.start));
        List<Interval> merged = new ArrayList<>();
        merged.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            Interval last = merged.get(merged.size() - 1);
            if (intervals[i].start <= last.end) {
                last.end = Math.max(last.end, intervals[i].end);
            } else {
                merged.add(intervals[i]);
            }
        }
        return merged;
    }
}

Python:

def merge_intervals(intervals):
    if not intervals:
        return []
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for i in range(1, len(intervals)):
        current = intervals[i]
        last = merged[-1]
        if current[0] <= last[1]:
            merged[-1] = (last[0], max(last[1], current[1]))
        else:
            merged.append(current)
    return merged

JavaScript:

function mergeIntervals(intervals) {
  if (intervals.length <= 1) return intervals;
  intervals.sort((a, b) => a[0] - b[0]);
  const merged = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const current = intervals[i];
    const last = merged[merged.length - 1];
    if (current[0] <= last[1]) {
      merged[merged.length - 1] = [last[0], Math.max(last[1], current[1])];
    } else {
      merged.push(current);
    }
  }
  return merged;
}

Example Problems

Meeting Rooms: Given an array of meeting time intervals, determine if a person could attend all meetings.
Insert Interval: Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
Minimum Number of Arrows to Burst Balloons: Given a set of intervals representing balloons, find the minimum number of arrows needed to burst all balloons.
Employee Free Time: Given the availability time slots of employees, find the intervals when none of the employees are available.
Merge Triplets: Extend the concept to merge triplets (start, middle, end) instead of pairs.
Intervals with overlapping ranges: Given an array of integer intervals (start, end), find all intervals that overlap at least one other interval
Find the maximum sum of non-overlapping intervals: Given an array of intervals with weights, find the maximum sum of weights that can be obtained by selecting non-overlapping intervals.
Find the number of intervals that contain a given number: Given an array of intervals and a number, find how many intervals contain that number.
Find the longest non-overlapping interval: Given an array of intervals, find the longest sequence of non-overlapping intervals.
Merge k Sorted Intervals: Extend the problem to handle k sorted lists of intervals, merging them into a single sorted list.

Mastering Merge Intervals: A Programmer's Guide

This blog post delves into the Merge Intervals technique, a common algorithmic pattern encountered in various software engineering problems. We'll explore the core concept, identify recurring patterns, and tackle problems of varying difficulty levels using Java, Python, and JavaScript.

Understanding Merge Intervals

The Merge Intervals problem essentially involves combining overlapping intervals into non-overlapping ones. An interval is typically represented as a pair of numbers, [start, end], denoting a range. The goal is to merge any intervals that share a common element.

Example:

Given the intervals [[1,3],[2,6],[8,10],[15,18]], the merged intervals would be [[1,6],[8,10],[15,18]]. Notice how [1,3] and [2,6] overlap and are merged into [1,6].

Pattern Identification:

The key pattern is sorting the intervals based on their start times. Once sorted, we can iteratively check for overlaps. If an overlap exists, we merge the intervals. If no overlap, we add the current interval to the result set.

Simple Approach (Easy Difficulty)

Sort: Sort the intervals by their start times.
Initialize: Create a result list to store the merged intervals. Add the first interval to the result.
Iterate: Iterate through the sorted intervals, starting from the second interval.
Check for Overlap: If the current interval's start time is less than or equal to the last interval's end time in the result list, merge them (update the end time of the last interval in the result).
Append: If there's no overlap, append the current interval to the result list.
Return: Return the result list.

Java Implementation (Easy):

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

class Interval {
    int start;
    int end;

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

public class MergeIntervalsEasy {
    public List<Interval> merge(Interval[] intervals) {
        if (intervals.length <= 1) return Arrays.asList(intervals);
        Arrays.sort(intervals, Comparator.comparingInt(a -> a.start));
        List<Interval> result = new ArrayList<>();
        result.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            Interval last = result.get(result.size() - 1);
            if (intervals[i].start <= last.end) {
                last.end = Math.max(last.end, intervals[i].end);
            } else {
                result.add(intervals[i]);
            }
        }
        return result;
    }
}

Python Implementation (Easy):

def merge_intervals(intervals):
    if len(intervals) <= 1:
        return intervals
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for i in range(1, len(intervals)):
        if intervals[i][0] <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], intervals[i][1])
        else:
            merged.append(intervals[i])
    return merged

JavaScript Implementation (Easy):

function mergeIntervals(intervals) {
    if (intervals.length <= 1) return intervals;
    intervals.sort((a, b) => a[0] - b[0]);
    const merged = [intervals[0]];
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] <= merged[merged.length - 1][1]) {
            merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], intervals[i][1]);
        } else {
            merged.push(intervals[i]);
        }
    }
    return merged;
}

Example Problems

(Easy):

Merge overlapping intervals. ([[1,3],[2,6],[8,10],[15,18]]) -> [[1,6],[8,10],[15,18]]

(Medium):

Insert a new interval into a list of non-overlapping intervals.
Find the minimum number of intervals to cover all points.

(Hard):

Meeting Rooms II (find the minimum number of meeting rooms required).
Employee Free Time (find the free time slots for employees).
Merge k Sorted Intervals.

Interview Questions

Explain your approach to solving the Merge Intervals problem.
What is the time and space complexity of your solution? How can it be optimized?
How would you handle edge cases, such as empty input or intervals with only one element?
Describe a scenario where this algorithm would be applicable in a real-world application.
How would you adapt your solution to handle intervals with different data types (e.g., strings)?

Related Guides:

Sorting and sweeping intervals: read Two Pointers.
Interval scheduling greedy choices: read Greedy Algorithms.
Merge multiple sorted ranges: read K-Way Merge.