Merge Intervals

1. Merging Overlapping Intervals

Step	Operation	Condition	Action
1. Sort	Sort intervals by start time	`intervals.sort((a,b) => a[0] - b[0])`	Ensures sequential processing
2. Initialize	Start with first interval	`merged = [intervals[0]]`	Base case for merging
3. Check Overlap	Compare end with next start	`if (last.end >= current.start)`	Intervals overlap or touch
4. Merge or Add	Extend end or add new interval	`last.end = max(last.end, current.end)`	Update merged result

Example: Merge overlapping intervals

function merge(intervals) {
    if (intervals.length <= 1) return intervals;
    
    // Sort by start time
    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 (last[1] >= current[0]) {
            // Overlapping - merge by extending end
            last[1] = Math.max(last[1], current[1]);
        } else {
            // No overlap - add as new interval
            merged.push(current);
        }
    }
    
    return merged;
}

// [[1,3],[2,6],[8,10],[15,18]] -> [[1,6],[8,10],[15,18]]
// Time: O(n log n), Space: O(n)

Note: When merging, use Math.max(last[1], current[1]) for the end time because current interval might be completely contained within the last interval.

2. Insert Interval Optimization

Phase	Strategy	Condition	Complexity
Before Insert	Add intervals ending before new interval	`interval[1] < newInterval[0]`	No overlap, add as-is
Merge Phase	Merge all overlapping intervals	`interval[0] <= newInterval[1]`	Update start/end bounds
After Insert	Add remaining intervals	`interval[0] > newInterval[1]`	No more overlaps
Optimization	No sorting needed - already sorted	Input guaranteed sorted	`O(n)` linear time

Example: Insert interval into sorted intervals

function insert(intervals, newInterval) {
    const result = [];
    let i = 0;
    
    // Phase 1: Add all intervals before newInterval
    while (i < intervals.length && intervals[i][1] < newInterval[0]) {
        result.push(intervals[i]);
        i++;
    }
    
    // Phase 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.push(newInterval);
    
    // Phase 3: Add remaining intervals
    while (i < intervals.length) {
        result.push(intervals[i]);
        i++;
    }
    
    return result;
}

// intervals = [[1,3],[6,9]], newInterval = [2,5]
// Output: [[1,5],[6,9]]

3. Interval Intersection Logic

Relationship	Condition	Intersection	Visual
Overlap Exists	`max(start1, start2) <= min(end1, end2)`	`[max(start1,start2), min(end1,end2)]`	Intervals share common region
No Overlap	`end1 < start2 \|\| end2 < start1`	Empty intersection	Completely separate intervals
One Contains Other	`start1 <= start2 && end1 >= end2`	Smaller interval is intersection	Nested intervals
Partial Overlap	Start of one < end of other	Overlapping region only	Crossing intervals

Example: Interval list intersections (two sorted lists)

function intervalIntersection(firstList, secondList) {
    const result = [];
    let i = 0, j = 0;
    
    while (i < firstList.length && j < secondList.length) {
        const [start1, end1] = firstList[i];
        const [start2, end2] = secondList[j];
        
        // Check if intervals overlap
        const start = Math.max(start1, start2);
        const end = Math.min(end1, end2);
        
        if (start <= end) {
            // Overlap exists
            result.push([start, end]);
        }
        
        // Move pointer of interval that ends first
        if (end1 < end2) {
            i++;
        } else {
            j++;
        }
    }
    
    return result;
}

// A = [[0,2],[5,10],[13,23],[24,25]]
// B = [[1,5],[8,12],[15,24],[25,26]]
// Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

4. Meeting Rooms Scheduling

Problem	Approach	Data Structure	Complexity
Can Attend All?	Sort by start, check if any overlap	Sorted array	`O(n log n)`
Min Meeting Rooms	Track concurrent meetings with heap	Min heap of end times	`O(n log n)`
Alternative: Sweep Line	Count +1 at start, -1 at end	Event array with timestamps	`O(n log n)`
Max Concurrent	Track maximum rooms in use at any time	Running count of active meetings	Peak value during sweep

Example: Can attend all meetings?

function canAttendMeetings(intervals) {
    if (intervals.length <= 1) return true;
    
    // Sort by start time
    intervals.sort((a, b) => a[0] - b[0]);
    
    // Check for any overlap
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < intervals[i-1][1]) {
            return false; // Overlap found
        }
    }
    
    return true;
}

// [[0,30],[5,10],[15,20]] -> false
// [[7,10],[2,4]] -> true

Example: Minimum meeting rooms needed

function minMeetingRooms(intervals) {
    if (intervals.length === 0) return 0;
    
    const starts = intervals.map(i => i[0]).sort((a,b) => a-b);
    const ends = intervals.map(i => i[1]).sort((a,b) => a-b);
    
    let rooms = 0;
    let maxRooms = 0;
    let startPtr = 0, endPtr = 0;
    
    while (startPtr < intervals.length) {
        if (starts[startPtr] < ends[endPtr]) {
            rooms++; // Meeting starts
            maxRooms = Math.max(maxRooms, rooms);
            startPtr++;
        } else {
            rooms--; // Meeting ends
            endPtr++;
        }
    }
    
    return maxRooms;
}

Example: Meeting rooms II with min heap (alternative)

function minMeetingRoomsHeap(intervals) {
    if (intervals.length === 0) return 0;
    
    // Sort by start time
    intervals.sort((a, b) => a[0] - b[0]);
    
    // Min heap to track end times of ongoing meetings
    const endTimes = [intervals[0][1]];
    
    for (let i = 1; i < intervals.length; i++) {
        const [start, end] = intervals[i];
        
        // If earliest ending meeting finished, reuse room
        if (endTimes[0] <= start) {
            endTimes.shift(); // Remove earliest end time
        }
        
        // Add current meeting's end time
        endTimes.push(end);
        endTimes.sort((a, b) => a - b); // Maintain min heap
    }
    
    return endTimes.length; // Number of rooms needed
}

// [[0,30],[5,10],[15,20]] -> 2

5. Non-overlapping Intervals Greedy

Strategy	Sort Key	Greedy Choice	Rationale
Max Non-overlapping	Sort by end time	Always pick interval ending earliest	Leaves most room for future intervals
Min Removals	Sort by end time	Keep intervals that end early	Removals = total - max non-overlapping
Interval Partitioning	Sort by start time	Assign to earliest available partition	Minimize number of partitions needed
Activity Selection	Sort by end time	Greedy end-time selection	Classic greedy algorithm proof

Example: Minimum number of intervals to remove

function eraseOverlapIntervals(intervals) {
    if (intervals.length <= 1) return 0;
    
    // Sort by end time (greedy choice)
    intervals.sort((a, b) => a[1] - b[1]);
    
    let count = 0;
    let end = intervals[0][1];
    
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < end) {
            // Overlaps with previous - remove this one
            count++;
        } else {
            // No overlap - update end time
            end = intervals[i][1];
        }
    }
    
    return count;
}

// [[1,2],[2,3],[3,4],[1,3]] -> 1 (remove [1,3])
// Greedy: Keep intervals ending earliest

Example: Maximum non-overlapping intervals (activity selection)

function maxNonOverlapping(intervals) {
    if (intervals.length === 0) return 0;
    
    // Sort by end time
    intervals.sort((a, b) => a[1] - b[1]);
    
    let count = 1; // First interval always included
    let end = intervals[0][1];
    
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= end) {
            // No overlap - include this interval
            count++;
            end = intervals[i][1];
        }
    }
    
    return count;
}

// Proof: Greedy choice optimal - interval ending earliest
// leaves maximum space for remaining intervals

6. Timeline Event Processing

Pattern	Event Types	Processing Order	Use Case
Start/End Events	+1 for start, -1 for end	Sort by time, then type (end before start)	Count active intervals at any time
Sweep Line	Process events in chronological order	Maintain running state across timeline	Skyline problem, interval coverage
Employee Free Time	Flatten all schedules, find gaps	Merge busy intervals, return gaps	Common free time across people
Point vs Interval	Events at specific times	Discrete events vs continuous ranges	Different collision detection logic

Example: Employee free time (flatten and find gaps)

function employeeFreeTime(schedule) {
    // Flatten all intervals
    const allIntervals = [];
    for (let employee of schedule) {
        allIntervals.push(...employee);
    }
    
    // Sort by start time
    allIntervals.sort((a, b) => a[0] - b[0]);
    
    // Merge overlapping intervals
    const merged = [allIntervals[0]];
    for (let i = 1; i < allIntervals.length; i++) {
        const last = merged[merged.length - 1];
        const curr = allIntervals[i];
        
        if (last[1] >= curr[0]) {
            last[1] = Math.max(last[1], curr[1]);
        } else {
            merged.push(curr);
        }
    }
    
    // Find gaps between merged intervals
    const freeTime = [];
    for (let i = 1; i < merged.length; i++) {
        freeTime.push([merged[i-1][1], merged[i][0]]);
    }
    
    return freeTime;
}

// schedule = [[[1,3],[4,6]], [[2,4]], [[6,8]]]
// Output: [[4,6]] is not available, [[6,6]] is gap -> No free time
// Actual output: [] (no common free time)

Example: Sweep line for maximum concurrent events

function maxConcurrentEvents(intervals) {
    const events = [];
    
    // Create start and end events
    for (let [start, end] of intervals) {
        events.push([start, 1]);   // Start event
        events.push([end, -1]);    // End event
    }
    
    // Sort events: by time, end events before start events
    events.sort((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0];
        return a[1] - b[1]; // End (-1) before start (1)
    });
    
    let current = 0;
    let maxConcurrent = 0;
    
    for (let [time, type] of events) {
        current += type;
        maxConcurrent = Math.max(maxConcurrent, current);
    }
    
    return maxConcurrent;
}

// [[0,30],[5,10],[15,20]] -> 2 concurrent meetings max

Merge Intervals Pattern Summary

Standard Merge: Sort by start, merge overlapping by extending end
Insert Interval: Three phases - before, merge, after (O(n) no sort)
Intersection: max(start1,start2) <= min(end1,end2)
Meeting Rooms: Min heap of end times or sweep line with events
Greedy Selection: Sort by end time, pick earliest ending
Sweep Line: Process start/end events chronologically

Note: When sorting intervals for merging, always sort by start time. For greedy maximum selection problems, sort by end time. For sweep line, process events in chronological order with tie-breaking rules (end before start at same time).

Warning: Be careful with boundary conditions: use < vs <= consistently. For example, [1,2] and [2,3] might be considered overlapping or adjacent depending on problem definition. Always clarify if endpoints are inclusive or exclusive.

Related Cheatsheets

Datastructures-algorithms