Interval Problems

🧭 When to Use This Pattern - Checklist

Pattern Recognition Checklist

✅ Use Interval Patterns When:

🎯 Time/Range Overlaps: Problems involving overlapping time periods, ranges, or segments
📊 Scheduling Conflicts: Managing meetings, events, or resource allocation in time
🔍 Merging Operations: Combining overlapping or adjacent intervals
⚡ Interval Queries: Finding intersections, gaps, or coverage between intervals
🎨 Optimization with Time: Maximizing/minimizing events within time constraints

❌ Don't Use Interval Patterns When:

🚫 Point-Based Problems: Dealing with individual points rather than ranges
🚫 Non-Temporal Data: Problems not involving time, ranges, or continuity
🚫 Complex Dependencies: Intervals with complex dependency relationships
🚫 Discrete Optimization: Problems better suited for DP or graph algorithms

🔍 Decision Flowchart:

                    ┌─────────────────────────────────┐
                    │    Problem Analysis Start       │
                    └─────────────┬───────────────────┘
                                  │
                    ┌─────────────▼───────────────────┐
                    │  Does problem involve ranges,   │
                    │  time periods, or intervals?    │
                    └─────────────┬───────────────────┘
                                  │ YES
                    ┌─────────────▼───────────────────┐
                    │  What operation is needed?      │
                    └─────────────┬───────────────────┘
                                  │
                    ┌─────────────▼───────────────────┐
                    │  Choose Pattern Type:           │
                    │                                 │
                    │  🔗 MERGE INTERVALS:            │
                    │      ✓ Combine overlapping      │
                    │      ✓ Sort by start time       │
                    │      ✓ Linear scan and merge    │
                    │                                 │
                    │  🏢 MEETING ROOMS:              │
                    │      ✓ Count simultaneous events│
                    │      ✓ Event start/end tracking │
                    │      ✓ Min heap for scheduling  │
                    │                                 │
                    │  📅 INTERVAL SCHEDULING:        │
                    │      ✓ Maximize non-overlapping │
                    │      ✓ Greedy by end time       │
                    │      ✓ Activity selection       │
                    │                                 │
                    │  🎯 POINT COVERAGE:             │
                    │      ✓ Minimum points to cover  │
                    │      ✓ Sweep line algorithms    │
                    └─────────────────────────────────┘

Merge Intervals

Core Pattern: Sort and Merge

The fundamental approach for merging intervals is to first sort them by start time, then iterate through and merge overlapping intervals. This ensures we process intervals in the correct order.

🌍 Real-World Applications:

📅 Calendar Systems: Merging overlapping appointments and events

🌐 Network Traffic: Combining time windows of high network usage

🏭 Production Planning: Merging overlapping production schedules

📊 Data Analysis: Combining time series data with overlapping periods

TypeScript

// 1. Basic Merge Intervals
function merge(intervals: number[][]): number[][] {
    if (intervals.length <= 1) return intervals;
    
    // Sort by start time
    intervals.sort((a, b) => a[0] - b[0]);
    
    const merged: number[][] = [intervals[0]];
    
    for (let i = 1; i < intervals.length; i++) {
        const current = intervals[i];
        const lastMerged = merged[merged.length - 1];
        
        // Check for overlap
        if (current[0] <= lastMerged[1]) {
            // Merge intervals
            lastMerged[1] = Math.max(lastMerged[1], current[1]);
        } else {
            // No overlap, add new interval
            merged.push(current);
        }
    }
    
    return merged;
}

// 2. Insert Interval
function insert(intervals: number[][], newInterval: number[]): number[][] {
    const result: number[][] = [];
    let i = 0;
    
    // Add all intervals that end before newInterval starts
    while (i < intervals.length && intervals[i][1] < newInterval[0]) {
        result.push(intervals[i]);
        i++;
    }
    
    // Merge overlapping intervals with newInterval
    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);
    
    // Add remaining intervals
    while (i < intervals.length) {
        result.push(intervals[i]);
        i++;
    }
    
    return result;
}

// 3. Meeting Rooms II - Minimum Rooms Needed
function minMeetingRooms(intervals: number[][]): number {
    if (intervals.length === 0) return 0;
    
    // Event point method
    const events: [number, number][] = [];
    
    for (const [start, end] of intervals) {
        events.push([start, 1]);   // Meeting starts
        events.push([end, -1]);   // Meeting ends
    }
    
    // Sort by time, with end events before start events at same time
    events.sort((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0];
        return a[1] - b[1]; // End (-1) comes before start (1)
    });
    
    let currentRooms = 0;
    let maxRooms = 0;
    
    for (const [time, type] of events) {
        currentRooms += type;
        maxRooms = Math.max(maxRooms, currentRooms);
    }
    
    return maxRooms;
}

// Example usage
function demonstrateIntervals(): void {
    console.log("Basic Merge:");
    console.log(merge([[1,3],[2,6],[8,10],[15,18]])); // [[1,6],[8,10],[15,18]]
    
    console.log("\nMinimum Meeting Rooms:");
    console.log(minMeetingRooms([[0,30],[5,10],[15,20]])); // 2
}

Python

# Interval Problems

# 1. Basic Merge Intervals
def merge(intervals):
    """Merge overlapping intervals"""
    if len(intervals) <= 1:
        return intervals
    
    # Sort by start time
    intervals.sort(key=lambda x: x[0])
    
    merged = [intervals[0]]
    
    for current in intervals[1:]:
        last_merged = merged[-1]
        
        # Check for overlap
        if current[0] <= last_merged[1]:
            # Merge intervals
            last_merged[1] = max(last_merged[1], current[1])
        else:
            # No overlap, add new interval
            merged.append(current)
    
    return merged

# 2. Insert Interval
def insert(intervals, new_interval):
    """Insert interval and merge if necessary"""
    result = []
    i = 0
    
    # Add all intervals that end before new_interval starts
    while i < len(intervals) and intervals[i][1] < new_interval[0]:
        result.append(intervals[i])
        i += 1
    
    # Merge overlapping intervals with new_interval
    while i < len(intervals) and intervals[i][0] <= new_interval[1]:
        new_interval[0] = min(new_interval[0], intervals[i][0])
        new_interval[1] = max(new_interval[1], intervals[i][1])
        i += 1
    result.append(new_interval)
    
    # Add remaining intervals
    while i < len(intervals):
        result.append(intervals[i])
        i += 1
    
    return result

# 3. Meeting Rooms II - Minimum Rooms Needed
def min_meeting_rooms(intervals):
    """Find minimum number of meeting rooms needed"""
    if not intervals:
        return 0
    
    import heapq
    
    # Sort by start time
    intervals.sort(key=lambda x: x[0])
    
    # Min heap to track end times of ongoing meetings
    heap = []
    
    for start, end in intervals:
        # If earliest ending meeting has ended, remove it
        if heap and heap[0] <= start:
            heapq.heappop(heap)
        
        # Add current meeting's end time
        heapq.heappush(heap, end)
    
    return len(heap)

# Example usage
def demonstrate_intervals():
    print("Basic Merge:")
    print(merge([[1,3],[2,6],[8,10],[15,18]]))  # [[1,6],[8,10],[15,18]]
    
    print("\nMinimum Meeting Rooms:")
    print(min_meeting_rooms([[0,30],[5,10],[15,20]]))  # 2

OCaml

open Printf

(* Interval type definition *)
type interval = { start: int; finish: int }

(* 1. Basic Merge Intervals *)
let merge intervals =
  if Array.length intervals <= 1 then intervals
  else begin
    (* Sort by start time *)
    Array.sort (fun a b -> compare a.start b.start) intervals;
    
    let merged = ref [intervals.(0)] in
    
    for i = 1 to Array.length intervals - 1 do
      let current = intervals.(i) in
      let last_merged = List.hd !merged in
      
      if current.start <= last_merged.finish then
        (* Merge intervals *)
        let updated = { start = last_merged.start; 
                       finish = max last_merged.finish current.finish } in
        merged := updated :: (List.tl !merged)
      else
        (* No overlap, add new interval *)
        merged := current :: !merged
    done;
    
    Array.of_list (List.rev !merged)
  end

(* Example usage *)
let demonstrate_intervals () =
  let intervals = [| {start=1; finish=3}; {start=2; finish=6}; 
                     {start=8; finish=10}; {start=15; finish=18} |] in
  let merged = merge intervals in
  printf "Merged intervals: ";
  Array.iter (fun {start; finish} -> printf "[%d,%d] " start finish) merged;
  print_newline ()

Problem Type	Time Complexity	Space Complexity	Key Insight
Basic Merge	O(n log n)	O(1)	Sort by start time, then linear merge
Insert Interval	O(n)	O(n)	Three phases: before, merge, after
Meeting Rooms	O(n log n)	O(n)	Min heap or event point method

🎯 Interview Tips & Pattern Recognition

Interview Strategy Guide

🔍 Recognizing Interval Problems:

Keywords to Watch: "intervals", "ranges", "overlapping", "merging", "scheduling", "meetings", "time periods"
Problem Structure: Input contains pairs representing start/end times or ranges
Common Operations: Merge, intersect, count overlaps, find gaps, optimize scheduling
Sorting Strategy: Usually sort by start time, sometimes by end time for greedy approaches

💡 Solution Patterns by Problem Type:

Merge Overlapping: Sort by start → Linear scan → Merge when overlap detected
Count Simultaneous: Event points method or min heap for active intervals
Find Non-overlapping: Greedy approach, sort by end time
Intersection/Union: Two pointers technique or sweep line algorithm

⚠️ Common Pitfalls:

Boundary Conditions: Clarify if [1,2] and [2,3] overlap (usually they don't)
Sorting Choice: Start time vs end time - choose based on problem requirements
Edge Cases: Empty input, single interval, identical intervals
Data Structure Choice: Array vs heap vs balanced tree - consider time complexity

🌟 Interview Success Framework:

📋 Step 1 - Clarify: "Are touching intervals [1,2] and [2,3] considered overlapping?"

🎯 Step 2 - Identify Pattern: "This looks like a merge/scheduling/counting problem"

📊 Step 3 - Choose Approach: "Sort by start time, then scan/merge/count"

💻 Step 4 - Implement: "Handle sorting, then apply the core algorithm"

🧪 Step 5 - Test Edge Cases: "Empty input, single interval, all overlapping"

DSA Interview Guide

✅ Use Interval Patterns When:

❌ Don't Use Interval Patterns When:

🔍 Recognizing Interval Problems:

💡 Solution Patterns by Problem Type:

⚠️ Common Pitfalls: