Skip to main content

​
Intervals

Interval problems involve working with ranges [start, end] and are common in scheduling, calendar, and resource allocation scenarios. The key is often sorting followed by a linear scan.

​
Core Concepts

​
Interval Representation

  • Inclusive: [start, end] - both endpoints included
  • Half-open: [start, end) - start included, end excluded
  • Tuple/Array: [start, end] or (start, end)

​
Common Operations

  • Overlap: Two intervals intersect
  • Merge: Combine overlapping intervals
  • Insert: Add new interval and merge
  • Intersection: Find common parts

​
Key Patterns & Techniques

​
1. Sort by Start Time

  • Sort intervals by start time
  • Linear scan to merge/process
  • Time: O(n log n) for sort + O(n) for scan

​
2. Merge Overlapping

  • Check if current overlaps with last merged
  • Extend end time if overlapping
  • Add new interval if not overlapping

​
3. Interval Intersection

  • Two pointers on two interval lists
  • Find overlap: max(start1, start2), min(end1, end2)
  • Advance pointer with earlier end

​
4. Meeting Rooms

  • Sort by start time
  • Use min heap for end times
  • Track concurrent meetings

​
Common Approaches

​
Merge Intervals

def merge(intervals: List[List[int]]) -> List[List[int]]:
    """
    Merge all overlapping intervals.
    Time: O(n log n), Space: O(n)
    """
    if not intervals:
        return []
    
    # Sort by start time
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    
    for current in intervals[1:]:
        last = merged[-1]
        
        # Check overlap: current.start <= last.end
        if current[0] <= last[1]:
            # Merge by extending end
            last[1] = max(last[1], current[1])
        else:
            # No overlap, add new interval
            merged.append(current)
    
    return merged

​
Insert Interval

def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    """
    Insert and merge new interval.
    Time: O(n), Space: O(n)
    """
    result = []
    i = 0
    n = len(intervals)
    
    # Add all intervals before newInterval
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1
    
    # Merge overlapping intervals
    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1
    
    result.append(newInterval)
    
    # Add remaining intervals
    while i < n:
        result.append(intervals[i])
        i += 1
    
    return result

​
Interval List Intersections

def intervalIntersection(A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
    """
    Find intersection of two interval lists.
    Time: O(m + n), Space: O(1) excluding output
    """
    result = []
    i = j = 0
    
    while i < len(A) and j < len(B):
        # Find intersection
        start = max(A[i][0], B[j][0])
        end = min(A[i][1], B[j][1])
        
        # If valid intersection
        if start <= end:
            result.append([start, end])
        
        # Move pointer with earlier end
        if A[i][1] < B[j][1]:
            i += 1
        else:
            j += 1
    
    return result

​
Meeting Rooms II (Min Rooms Needed)

import heapq

def minMeetingRooms(intervals: List[List[int]]) -> int:
    """
    Find minimum number of meeting rooms needed.
    Time: O(n log n), Space: O(n)
    """
    if not intervals:
        return 0
    
    # Sort by start time
    intervals.sort(key=lambda x: x[0])
    
    # Min heap of end times
    heap = []
    
    for start, end in intervals:
        # If earliest meeting ended, reuse room
        if heap and heap[0] <= start:
            heapq.heappop(heap)
        
        # Add current meeting's end time
        heapq.heappush(heap, end)
    
    # Heap size = number of rooms needed
    return len(heap)

​
Non-overlapping Intervals (Min Removals)

def eraseOverlapIntervals(intervals: List[List[int]]) -> int:
    """
    Minimum removals to make non-overlapping.
    Time: O(n log n), Space: O(1)
    """
    if not intervals:
        return 0
    
    # Sort by end time (greedy)
    intervals.sort(key=lambda x: x[1])
    
    count = 0
    prev_end = intervals[0][1]
    
    for i in range(1, len(intervals)):
        if intervals[i][0] < prev_end:
            # Overlapping, remove current
            count += 1
        else:
            # Non-overlapping, update end
            prev_end = intervals[i][1]
    
    return count

​
Problems in This Category

016. Merge Intervals

Medium | Frequency: 77.9%Sort by start, merge overlapping intervals in linear scan.

088. Interval List Intersections

Medium | Frequency: 32.0%Two pointers to find overlaps between two sorted interval lists.

077. Car Pooling

**Medium” | Frequency: 40.7%Track capacity at each location using interval scheduling.

​
Complexity Characteristics

PatternTime ComplexitySpace ComplexityKey Insight
Merge IntervalsO(n log n)O(n)Sort by start, linear merge
Insert IntervalO(n)O(n)Three phases: before, merge, after
Interval IntersectionO(m + n)O(k)Two pointers, k = output size
Meeting RoomsO(n log n)O(n)Min heap tracks room availability
Min RemovalsO(n log n)O(1)Sort by end, greedy selection

​
Interview Tips

​
Pattern Recognition

  • “Merge overlapping…” → Sort by start, scan and merge
  • “Insert interval” → Three-phase approach
  • “Minimum rooms/resources” → Heap of end times
  • “Intersection of intervals” → Two pointers
  • “Non-overlapping intervals” → Sort by end, greedy
  • “Point in time queries” → Sweep line algorithm

​
Common Mistakes

  • Not sorting intervals first
  • Wrong overlap condition (use <= vs <)
  • Forgetting to handle edge cases (empty, single interval)
  • Not considering touching intervals [1,2] and [2,3]
  • Off-by-one errors in interval boundaries

​
Key Insights

  1. Sort first - enables O(n) scan after O(n log n) sort
  2. Overlap condition: current.start <= last.end
  3. Merge by extending end: max(last.end, current.end)
  4. Sort by end for greedy - scheduling problems
  5. Heap tracks concurrent events - meeting rooms
  6. Two pointers for two lists - intersection problems

​
Overlap Detection

​
Two intervals overlap if:

# Intervals: [a1, a2] and [b1, b2]
# Overlap if: max(a1, b1) <= min(a2, b2)

def overlaps(a, b):
    return a[0] <= b[1] and b[0] <= a[1]
    # Equivalent to: max(a[0], b[0]) <= min(a[1], b[1])

​
Types of Overlap

Case 1: Partial overlap
  [-----)       a
      [-----)   b
      [---)     intersection

Case 2: Complete overlap
  [--------)    a
    [---)       b
    [---)       intersection

Case 3: No overlap
  [-----)       a
          [---) b
  (no intersection)

Case 4: Touching (depends on inclusive/exclusive)
  [-----)       a
        [---)   b
  May or may not merge based on problem

​
Advanced Patterns

​
Sweep Line Algorithm

def maximumPopulation(logs: List[List[int]]) -> int:
    """
    Find year with maximum population.
    Sweep line: track events (birth/death).
    Time: O(n log n), Space: O(n)
    """
    events = []
    
    for birth, death in logs:
        events.append((birth, 1))   # Birth increases population
        events.append((death, -1))  # Death decreases population
    
    events.sort()
    
    max_pop = 0
    max_year = 0
    current_pop = 0
    
    for year, change in events:
        current_pop += change
        
        if current_pop > max_pop:
            max_pop = current_pop
            max_year = year
    
    return max_year

​
Range Module (Interval Set)

from bisect import bisect_left, bisect_right

class RangeModule:
    """
    Maintain set of non-overlapping intervals.
    Time: O(n) per operation worst case
    """
    def __init__(self):
        self.intervals = []  # Sorted non-overlapping intervals
    
    def addRange(self, left: int, right: int) -> None:
        # Find overlapping intervals
        i = bisect_left(self.intervals, [left, right])
        j = bisect_right(self.intervals, [left, right])
        
        # Merge with overlapping intervals
        if i > 0 and self.intervals[i-1][1] >= left:
            i -= 1
            left = self.intervals[i][0]
        
        if j < len(self.intervals) and self.intervals[j][0] <= right:
            right = self.intervals[j][1]
            j += 1
        
        # Replace overlapping intervals with merged
        self.intervals[i:j] = [[left, right]]
    
    def queryRange(self, left: int, right: int) -> bool:
        i = bisect_right(self.intervals, [left, right])
        
        return (i > 0 and 
                self.intervals[i-1][0] <= left and 
                right <= self.intervals[i-1][1])
    
    def removeRange(self, left: int, right: int) -> None:
        i = bisect_left(self.intervals, [left, right])
        j = bisect_right(self.intervals, [left, right])
        
        new_intervals = []
        
        # Check if need to split interval before
        if i > 0 and self.intervals[i-1][1] > left:
            i -= 1
            if self.intervals[i][0] < left:
                new_intervals.append([self.intervals[i][0], left])
        
        # Check if need to split interval after
        if j < len(self.intervals) and self.intervals[j][0] < right:
            if self.intervals[j][1] > right:
                new_intervals.append([right, self.intervals[j][1]])
            j += 1
        
        self.intervals[i:j] = new_intervals

​
Employee Free Time

def employeeFreeTime(schedule: List[List[List[int]]]) -> List[List[int]]:
    """
    Find common free time for all employees.
    Time: O(n log n), n = total intervals
    """
    # Flatten and sort all intervals
    intervals = []
    for employee in schedule:
        intervals.extend(employee)
    
    intervals.sort(key=lambda x: x[0])
    
    # Merge intervals to find busy time
    merged = [intervals[0]]
    for current in intervals[1:]:
        last = merged[-1]
        if current[0] <= last[1]:
            last[1] = max(last[1], current[1])
        else:
            merged.append(current)
    
    # Gaps between merged intervals are free time
    free_time = []
    for i in range(len(merged) - 1):
        free_time.append([merged[i][1], merged[i+1][0]])
    
    return free_time

​
Decision Tree

Are intervals sorted?
├─ No: Sort by start time (or end for greedy)
└─ Yes: Proceed
    ├─ Need to merge overlapping? → Linear scan with merge
    ├─ Insert new interval? → Three-phase approach
    ├─ Find intersections? → Two pointers
    ├─ Count concurrent events? → Heap or sweep line
    └─ Minimize removals? → Sort by end, greedy
Pro Tip: Almost all interval problems start with sorting. Sort by start time for most problems, but sort by end time for scheduling/greedy problems (like minimum removals). The overlap condition is current.start <= last.end.

Build docs developers (and LLMs) love

Get started for freeTalk to us