Merge Intervals Pattern¶

Overview¶

Process overlapping intervals by sorting and merging/comparing adjacent intervals. Essential for scheduling, resource allocation, and range problems.

When to Use¶

Merging overlapping intervals
Finding intersections between interval lists
Inserting into sorted intervals
Meeting room scheduling
Finding gaps/free slots
Interval coverage problems

Merge Intervals Step-by-Step

Interval Relationships: 1. No Overlap: a ends before b starts → keep separate 2. Overlap: a ends after b starts → merge to [a.start, max(a.end, b.end)] 3. Complete Overlap: one contains the other → keep the larger 4. Adjacent: a ends where b starts → optionally merge

Template Code¶

Merge Overlapping Intervals¶

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

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

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

    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] <= current[1]) {
            // Overlap - extend current interval
            current[1] = Math.max(current[1], intervals[i][1]);
        } else {
            // No overlap - add current and start new
            merged.add(current);
            current = intervals[i];
        }
    }
    merged.add(current);  // Don't forget last interval

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

Insert Interval¶

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

    // Add all intervals before newInterval
    while (i < n && intervals[i][1] < newInterval[0]) {
        result.add(intervals[i]);
        i++;
    }

    // Merge overlapping intervals
    while (i < n && 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);

    // Add remaining intervals
    while (i < n) {
        result.add(intervals[i]);
        i++;
    }

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

Interval List Intersections¶

public int[][] intervalIntersection(int[][] A, int[][] B) {
    List<int[]> result = new ArrayList<>();
    int i = 0, j = 0;

    while (i < A.length && j < B.length) {
        // Find intersection
        int start = Math.max(A[i][0], B[j][0]);
        int end = Math.min(A[i][1], B[j][1]);

        if (start <= end) {
            result.add(new int[]{start, end});
        }

        // Move pointer with smaller end
        if (A[i][1] < B[j][1]) {
            i++;
        } else {
            j++;
        }
    }

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

Meeting Rooms II (Min Rooms Needed)¶

public int minMeetingRooms(int[][] intervals) {
    if (intervals.length == 0) return 0;

    int[] starts = new int[intervals.length];
    int[] ends = new int[intervals.length];

    for (int i = 0; i < intervals.length; i++) {
        starts[i] = intervals[i][0];
        ends[i] = intervals[i][1];
    }

    Arrays.sort(starts);
    Arrays.sort(ends);

    int rooms = 0, endPtr = 0;

    for (int i = 0; i < starts.length; i++) {
        if (starts[i] < ends[endPtr]) {
            rooms++;  // Need new room
        } else {
            endPtr++;  // Reuse freed room
        }
    }

    return rooms;
}

// Alternative with Min-Heap
public int minMeetingRoomsHeap(int[][] intervals) {
    if (intervals.length == 0) return 0;

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

    PriorityQueue<Integer> heap = new PriorityQueue<>();  // End times

    for (int[] interval : intervals) {
        if (!heap.isEmpty() && heap.peek() <= interval[0]) {
            heap.poll();  // Room freed up
        }
        heap.offer(interval[1]);  // Book the room
    }

    return heap.size();
}

Meeting Rooms (Can Attend All)¶

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

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

Employee Free Time¶

public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
    List<Interval> allIntervals = new ArrayList<>();

    // Flatten all intervals
    for (List<Interval> employee : schedule) {
        allIntervals.addAll(employee);
    }

    // Sort by start time
    allIntervals.sort((a, b) -> a.start - b.start);

    List<Interval> result = new ArrayList<>();
    int prevEnd = allIntervals.get(0).end;

    for (int i = 1; i < allIntervals.size(); i++) {
        Interval curr = allIntervals.get(i);

        if (curr.start > prevEnd) {
            // Gap found - free time!
            result.add(new Interval(prevEnd, curr.start));
        }
        prevEnd = Math.max(prevEnd, curr.end);
    }

    return result;
}

Non-overlapping Intervals (Min Removals)¶

public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0) return 0;

    // Sort by end time (greedy: keep shorter intervals)
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

    int removals = 0;
    int prevEnd = intervals[0][1];

    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < prevEnd) {
            removals++;  // Overlap - remove current
        } else {
            prevEnd = intervals[i][1];
        }
    }

    return removals;
}

Minimum Number of Arrows to Burst Balloons¶

public int findMinArrowShots(int[][] points) {
    if (points.length == 0) return 0;

    // Sort by end position
    Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));

    int arrows = 1;
    int arrowPos = points[0][1];

    for (int i = 1; i < points.length; i++) {
        if (points[i][0] > arrowPos) {
            // Need new arrow
            arrows++;
            arrowPos = points[i][1];
        }
    }

    return arrows;
}

Time & Space Complexity¶

Problem	Time	Space
Merge intervals	O(n log n)	O(n)
Insert interval	O(n)	O(n)
Interval intersection	O(n + m)	O(n + m)
Meeting rooms II	O(n log n)	O(n)
Non-overlapping	O(n log n)	O(1)

Common Interview Questions¶

Merge Intervals - Combine overlapping intervals
Insert Interval - Insert and merge if needed
Interval List Intersections - Find all intersections
Meeting Rooms - Can attend all meetings?
Meeting Rooms II - Min rooms needed
Non-overlapping Intervals - Min removals for no overlap
Minimum Number of Arrows - Burst overlapping balloons
Employee Free Time - Find common free time
Add Bold Tag in String - Merge bold intervals
Range Module - Add/remove/query ranges
My Calendar I, II, III - Book without K overlaps
Car Pooling - Can complete all trips?

Tips & Tricks¶

Always sort by start time (or end time for greedy)
Sorting by end time often helps minimize selections
Use min-heap for tracking "currently active" intervals
Two-pointer works for intersection of sorted lists
For "min removals": sort by end, greedily keep non-overlapping
Watch for edge cases: adjacent intervals, single interval
Integer overflow: use Integer.compare() for sorting