Interval Scheduling Patterns

1. Minimum Meeting Rooms Required

Approach	Method	Time	Space
Min Heap	Track end times of ongoing meetings	`O(n log n)`	`O(n)`
Chronological Ordering	Separate start/end events, sort and scan	`O(n log n)`	`O(n)`
Sweep Line	Event-driven: +1 for start, -1 for end	`O(n log n)`	`O(n)`
Brute Force	Check max overlaps at each point	`O(n^2)`	Not recommended

Example: Min heap approach

function minMeetingRooms(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 minHeap = new MinPriorityQueue({ priority: x => x });
    
    minHeap.enqueue(intervals[0][1]); // First meeting's end time
    
    for (let i = 1; i < intervals.length; i++) {
        const [start, end] = intervals[i];
        
        // If earliest ending meeting finished before current starts
        if (minHeap.front().element <= start) {
            minHeap.dequeue(); // Reuse this room
        }
        
        // Add current meeting's end time
        minHeap.enqueue(end);
    }
    
    // Heap size = number of rooms needed
    return minHeap.size();
}

// Example: [[0,30],[5,10],[15,20]]
// Sort: [[0,30],[5,10],[15,20]] (already sorted)
// Process [0,30]: heap = [30]
// Process [5,10]: 30 > 5, heap = [10,30]
// Process [15,20]: 10 <= 15, reuse room, heap = [20,30]
// Result: 2 rooms

Example: Chronological ordering

function minMeetingRoomsChronological(intervals) {
    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 endPointer = 0;
    
    for (let i = 0; i < starts.length; i++) {
        // If a meeting ends before or when current starts
        if (starts[i] >= ends[endPointer]) {
            rooms--; // Free up a room
            endPointer++;
        }
        
        rooms++; // Allocate room for current meeting
    }
    
    return rooms;
}

// Example: [[0,30],[5,10],[15,20]]
// starts: [0, 5, 15]
// ends:   [10, 20, 30]
// 
// i=0, start=0: rooms=1
// i=1, start=5: 5 < 10, rooms=2
// i=2, start=15: 15 >= 10, rooms=2-1+1=2
// Result: 2 rooms

Example: Sweep line with events

function minMeetingRoomsSweep(intervals) {
    const events = [];
    
    // Create start and end events
    for (const [start, end] of intervals) {
        events.push([start, 1]);   // Meeting starts (+1)
        events.push([end, -1]);    // Meeting ends (-1)
    }
    
    // Sort events: by time, then ends before starts (tie-breaking)
    events.sort((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0];
        return a[1] - b[1]; // -1 before 1 (end before start)
    });
    
    let rooms = 0;
    let maxRooms = 0;
    
    for (const [time, delta] of events) {
        rooms += delta;
        maxRooms = Math.max(maxRooms, rooms);
    }
    
    return maxRooms;
}

// Example: [[0,30],[5,10],[15,20]]
// Events: [[0,1],[5,1],[10,-1],[15,1],[20,-1],[30,-1]]
// Process: 0→1, 5→2, 10→1, 15→2, 20→1, 30→0
// Max: 2 rooms

Note: When sorting events at the same time, end events must come before start events (-1 before +1). This ensures a meeting ending at time T frees the room before a meeting starting at time T occupies it. Without this tie-breaking, we'd incorrectly count an extra room.

2. Employee Free Time Problem

Approach	Method	Time	Space
Merge All Intervals	Flatten, sort, merge, find gaps	`O(n log n)`	`O(n)`
Priority Queue	K-way merge of sorted lists	`O(n log k)`	`O(k)`
Sweep Line	Event processing for busy periods	`O(n log n)`	`O(n)`
Two Pointers	If each employee has 1 interval only	`O(n log n)`	`O(1)`

Example: Flatten and merge approach

function employeeFreeTime(schedule) {
    // Flatten all intervals into single array
    const intervals = [];
    for (const employee of schedule) {
        for (const interval of employee) {
            intervals.push(interval);
        }
    }
    
    // Sort by start time
    intervals.sort((a, b) => a.start - b.start);
    
    // Merge overlapping intervals
    const merged = [intervals[0]];
    
    for (let i = 1; i < intervals.length; i++) {
        const current = intervals[i];
        const last = merged[merged.length - 1];
        
        if (current.start <= last.end) {
            // Overlapping or adjacent - merge
            last.end = Math.max(last.end, current.end);
        } else {
            // Gap found - but don't add yet
            merged.push(current);
        }
    }
    
    // Find gaps between merged intervals
    const freeTime = [];
    for (let i = 1; i < merged.length; i++) {
        const gapStart = merged[i - 1].end;
        const gapEnd = merged[i].start;
        
        if (gapStart < gapEnd) {
            freeTime.push(new Interval(gapStart, gapEnd));
        }
    }
    
    return freeTime;
}

// Example: [[[1,3],[4,6]], [[2,4]], [[2,5],[9,12]]]
// Flattened: [[1,3],[4,6],[2,4],[2,5],[9,12]]
// Sorted: [[1,3],[2,4],[2,5],[4,6],[9,12]]
// Merged: [[1,6],[9,12]]
// Free time: [[6,9]]

Example: Priority queue k-way merge

function employeeFreeTimePQ(schedule) {
    // Min heap: [interval, employeeIndex, intervalIndex]
    const pq = new MinPriorityQueue({ 
        priority: x => x[0].start 
    });
    
    // Initialize with first interval of each employee
    for (let i = 0; i < schedule.length; i++) {
        if (schedule[i].length > 0) {
            pq.enqueue([schedule[i][0], i, 0]);
        }
    }
    
    const freeTime = [];
    let prevEnd = pq.front().element[0].start;
    
    while (!pq.isEmpty()) {
        const [interval, empIdx, intIdx] = pq.dequeue().element;
        
        // Found a gap
        if (prevEnd < interval.start) {
            freeTime.push(new Interval(prevEnd, interval.start));
        }
        
        prevEnd = Math.max(prevEnd, interval.end);
        
        // Add next interval from same employee
        if (intIdx + 1 < schedule[empIdx].length) {
            pq.enqueue([
                schedule[empIdx][intIdx + 1],
                empIdx,
                intIdx + 1
            ]);
        }
    }
    
    return freeTime;
}

// More efficient when k (employees) << n (total intervals)
// O(n log k) vs O(n log n)

3. Interval List Intersections

Approach	Technique	Time	Space
Two Pointers	Compare intervals from both lists	`O(m + n)`	`O(1)`
Intersection Logic	max(start1, start2) to min(end1, end2)	Overlaps if start ≤ end	Simple and elegant
Advance Pointer	Move pointer of interval that ends first	Ensures no interval missed	Critical for correctness
Multiple Lists	Use priority queue for k lists	`O(n log k)`	Generalization

Example: Two pointers intersection

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];
        
        // Calculate intersection
        const startIntersection = Math.max(start1, start2);
        const endIntersection = Math.min(end1, end2);
        
        // Valid intersection exists
        if (startIntersection <= endIntersection) {
            result.push([startIntersection, endIntersection]);
        }
        
        // Advance pointer of interval that ends first
        if (end1 < end2) {
            i++;
        } else {
            j++;
        }
    }
    
    return result;
}

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

Example: Visualizing intersection logic

// Understanding intersection calculation:
function hasIntersection(interval1, interval2) {
    const [start1, end1] = interval1;
    const [start2, end2] = interval2;
    
    // No intersection cases:
    // 1. interval1 completely before interval2: end1 < start2
    // 2. interval2 completely before interval1: end2 < start1
    
    // Has intersection if neither case is true:
    return !(end1 < start2 || end2 < start1);
}

function getIntersection(interval1, interval2) {
    const [start1, end1] = interval1;
    const [start2, end2] = interval2;
    
    const start = Math.max(start1, start2);
    const end = Math.min(end1, end2);
    
    // Valid if start <= end
    return start <= end ? [start, end] : null;
}

// Key insight: 
// Intersection start = max of two starts (later one)
// Intersection end = min of two ends (earlier one)
// Valid only if start <= end

// Examples:
// [1,5] ∩ [3,7] = [max(1,3), min(5,7)] = [3,5] ✓
// [1,3] ∩ [5,7] = [max(1,5), min(3,7)] = [5,3] ✗ (5 > 3)

4. Insert Interval and Merge

Step	Action	Condition	Complexity
1. Add Before	Add intervals completely before new interval	`interval.end < newInterval.start`	Direct copy
2. Merge Overlapping	Merge all overlapping intervals	`interval.start <= newInterval.end`	Update boundaries
3. Add After	Add remaining intervals after new interval	`interval.start > newInterval.end`	Direct copy
In-place Option	Modify input array instead of creating new	More complex pointer management	`O(1)` space

Example: Insert and merge interval

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

// Example: intervals = [[1,3],[6,9]], newInterval = [2,5]
// Step 1: No intervals end before 2
// Step 2: [1,3] overlaps, merge to [1,5]
// Step 3: Add [6,9]
// Result: [[1,5],[6,9]]

// Example: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]
//          newInterval = [4,8]
// Step 1: Add [1,2]
// Step 2: Merge [3,5],[6,7],[8,10] -> [3,10]
// Step 3: Add [12,16]
// Result: [[1,2],[3,10],[12,16]]

Example: Alternative approach with three passes

function insertAlternative(intervals, newInterval) {
    const result = [];
    let [newStart, newEnd] = newInterval;
    let inserted = false;
    
    for (const [start, end] of intervals) {
        if (end < newStart) {
            // Current interval completely before new
            result.push([start, end]);
        } else if (start > newEnd) {
            // Current interval completely after new
            if (!inserted) {
                result.push([newStart, newEnd]);
                inserted = true;
            }
            result.push([start, end]);
        } else {
            // Overlapping - expand new interval
            newStart = Math.min(newStart, start);
            newEnd = Math.max(newEnd, end);
        }
    }
    
    // If not inserted yet, add at end
    if (!inserted) {
        result.push([newStart, newEnd]);
    }
    
    return result;
}

// Single pass through intervals
// Track whether merged interval has been added

5. Task Scheduler Problem (Greedy)

Approach	Strategy	Formula	Complexity
Greedy Max Frequency	Schedule most frequent task first with cooldown	`max(n, (maxFreq-1)*cooldown + tiesCount)`	`O(n)`
Heap Simulation	Use max heap + cooldown queue	Simulate actual scheduling	`O(n log 26)`
Greedy Formula	Calculate without simulation	Slots needed = max of tasks or formula	`O(n)`
Idle Slots	Count idle time needed	`(maxFreq-1) * cooldown - other tasks`	Alternative view

Example: Greedy formula approach

function leastInterval(tasks, n) {
    // Count frequency of each task
    const freq = new Array(26).fill(0);
    for (const task of tasks) {
        freq[task.charCodeAt(0) - 'A'.charCodeAt(0)]++;
    }
    
    // Find max frequency
    const maxFreq = Math.max(...freq);
    
    // Count how many tasks have max frequency
    const maxCount = freq.filter(f => f === maxFreq).length;
    
    // Calculate minimum intervals
    // Pattern: (A _ _ A _ _ A) for maxFreq=3, cooldown=2
    // Partitions: (maxFreq - 1)
    // Each partition size: (n + 1) where n is cooldown
    // Last partition: maxCount tasks
    
    const partitions = maxFreq - 1;
    const partitionSize = n + 1;
    const emptySlots = partitions * partitionSize;
    const availableSlots = emptySlots + maxCount;
    const idles = Math.max(0, availableSlots - tasks.length);
    
    return tasks.length + idles;
}

// Alternative cleaner formula:
function leastIntervalFormula(tasks, n) {
    const freq = new Array(26).fill(0);
    for (const task of tasks) {
        freq[task.charCodeAt(0) - 'A'.charCodeAt(0)]++;
    }
    
    const maxFreq = Math.max(...freq);
    const maxCount = freq.filter(f => f === maxFreq).length;
    
    // Either all tasks fit, or need idle slots
    return Math.max(
        tasks.length,
        (maxFreq - 1) * (n + 1) + maxCount
    );
}

// Example: tasks = ["A","A","A","B","B","B"], n = 2
// Frequency: A=3, B=3
// maxFreq = 3, maxCount = 2
// Formula: (3-1)*(2+1) + 2 = 2*3 + 2 = 8
// Schedule: A B _ A B _ A B
// Result: 8

Example: Heap simulation approach

function leastIntervalHeap(tasks, n) {
    // Count frequencies
    const freq = {};
    for (const task of tasks) {
        freq[task] = (freq[task] || 0) + 1;
    }
    
    // Max heap of frequencies
    const maxHeap = new MaxPriorityQueue({ priority: x => x });
    for (const count of Object.values(freq)) {
        maxHeap.enqueue(count);
    }
    
    let time = 0;
    
    while (!maxHeap.isEmpty()) {
        const temp = [];
        
        // Try to schedule n+1 tasks (or until heap empty)
        for (let i = 0; i < n + 1; i++) {
            if (!maxHeap.isEmpty()) {
                const count = maxHeap.dequeue().element;
                if (count > 1) {
                    temp.push(count - 1);
                }
            }
        }
        
        // Add remaining tasks back to heap
        for (const count of temp) {
            maxHeap.enqueue(count);
        }
        
        // If heap not empty, full cycle; else just processed tasks
        time += maxHeap.isEmpty() ? temp.length + 1 : n + 1;
    }
    
    return time;
}

// Simulates actual scheduling cycle by cycle
// Each cycle: schedule up to (n+1) different tasks
// More intuitive but slower than formula approach

Note: Task Scheduler formula derivation: With max frequency F and cooldown N, we need F-1 complete "frames" of size N+1 (to satisfy cooldown), plus the final batch of tasks with max frequency. The answer is max(tasks.length, (F-1)*(N+1) + maxCount) because if we have enough task variety, no idle time is needed.

Summary: Interval Scheduling Patterns

Minimum Meeting Rooms: Min heap tracking end times, or chronological ordering of starts/ends, or sweep line with events - all O(n log n)
Min Heap Pattern: Sort by start, maintain heap of end times, reuse room if earliest end ≤ current start, heap size = rooms needed
Chronological Pattern: Separate sorted start/end arrays, two pointers, increment rooms on start, decrement on end
Sweep Line Events: Create [time, delta] events, sort with tie-breaking (ends before starts), track running count, record max
Employee Free Time: Flatten all intervals, sort, merge overlapping, gaps between merged = free time - O(n log n)
K-way Merge: Priority queue merging k sorted lists - O(n log k) more efficient when k << n
Interval Intersection: Two pointers, intersection = [max(start1,start2), min(end1,end2)], valid if start ≤ end, advance pointer of interval ending first
Insert Interval: Three phases: add before, merge overlapping, add after - O(n) single pass
Merge While Inserting: Expand new interval boundaries while overlapping, track insertion flag to avoid duplicates
Task Scheduler Greedy: Formula: max(tasks.length, (maxFreq-1)*(cooldown+1) + maxCount) - O(n) time
Scheduler Intuition: Most frequent task creates frames, other tasks fill frames, maxCount tasks with same max frequency go together in final frame
Heap Simulation: Max heap of frequencies, each cycle schedule up to cooldown+1 tasks, decrement and re-add - more intuitive but slower
Common Pattern: Sort intervals, use greedy or data structure (heap/events), handle overlaps, O(n log n) typical complexity

Related Cheat Sheets

Datastructures Algorithms