📚 Merge Intervals – Java Cheat Sheet (One Page)

📌 What Is It?

The Merge Intervals pattern involves working with overlapping intervals. The goal is to merge overlapping intervals or perform operations like insertion, intersection, or removal of intervals.

Sort intervals by their start time
Iterate through intervals and merge overlapping ones
Use a result list to store merged intervals

🧱 Pattern Template

public int[][] merge(int[][] intervals) {
    if (intervals.length <= 1) return intervals;

    // Sort intervals by start time
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

    List 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 (currentEnd >= nextStart) {
            // Overlapping intervals, merge them
            currentInterval[1] = Math.max(currentEnd, nextEnd);
        } else {
            // Non-overlapping interval, add to result
            currentInterval = interval;
            result.add(currentInterval);
        }
    }

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

✅ Use Cases

Merging overlapping intervals
Finding gaps between intervals
Interval insertion or intersection

📘 Common LeetCode Problems

56: Merge Intervals [Medium] Sorting, Intervals
57: Insert Interval [Medium] Sorting, Intervals
759: Employee Free Time [Hard] Sorting, Intervals
253: Meeting Rooms II [Medium] Heap, Intervals
986: Interval List Intersections [Medium] Two Pointers, Intervals

🧪 Example: Merge Intervals

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Intervals [1,3] and [2,6] overlap, so they are merged into [1,6].

💡 Pro Tips

Always sort intervals by their start time before processing
Use a list to store merged intervals dynamically
Edge cases: empty intervals, single interval, fully overlapping intervals