Topic 13: Intervals

Key-Intuition: Interval problems generally hinge on sorting endpoints, covering overlaps, and greedy allocation.

In fact, here’s a framework of thought for Greedy Algos to juxtapose with this section:

Canonical Questions #

Merge & Insert Intervals #

• Merge overlapping intervals, insert new interval maintaining order

Problems #

1. Merge Intervals (56)

   It’s a linear scan alright (after sorting intervals using the start time), we have a working accumulator that we keep making reference to.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

   from typing import List class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: if not intervals: return [] # Sort intervals based on start time intervals.sort(key=lambda x: x[0]) merged_intervals = [intervals[0]] for start, end in intervals[1:]: last_merged_start, last_merged_end = merged_intervals[-1] if start <= last_merged_end: # Overlapping intervals merged_intervals[-1][1] = max(last_merged_end, end) # Merge else: merged_intervals.append([start, end]) # No overlap, add new return merged_intervals

   Code Snippet 1: Merge Intervals (56)
   Pattern Extraction

   Core Insight: Sort intervals by start time. Iterate, maintaining a current merged interval. If the next interval overlaps (its start \(\leq\) current end), extend the current end. Otherwise, close the current interval and start a new one. Pattern Name: Sort-and-Merge Sweep Canonical Section: Intervals > Overlap Resolution Recognition Signals:

   • “Merge overlapping intervals”
   • Input is a list of \[start, end\] pairs
   • Need to produce a list of non-overlapping intervals covering the same range Anti-Signals:
     • Intervals are already sorted – skip the sort step
     • Need to INSERT a new interval and merge – similar but adds an insertion step. Connects to LC 57
     • Need to find the minimum number of intervals to REMOVE to make non-overlapping – sort by end time, greedy. Connects to LC 435 Decision Point: Merging = sort by start, extend. Removing for non-overlap = sort by end, greedy (activity selection). The sorting key differs between the two problems.
   Pitfalls and Misconceptions

   1. Trap: Forgetting to append the last accumulated interval. Why: The merge loop processes intervals upon encountering the NEXT non-overlapping one. The last interval never encounters a “next” and gets dropped. Correction: After the loop, append the current accumulated interval: merged.append([start, end]).
   2. Trap: Sorting by end time instead of start time. Why: Sorting by start time ensures we process intervals left-to-right and can extend rightward. Sorting by end time breaks the merge logic (intervals can start before the current merge window). Correction: Sort by interval[0] (start time).
   3. Trap: Using = instead of =<= for the overlap check. Why: \[1,4\] and \[4,5\] touch at the boundary. Whether they “overlap” depends on the problem definition. For LC 56, touching intervals SHOULD be merged. Correction: Use next_start < current_end= (inclusive) for the overlap check.
   Problem Mutations

   1. What if you needed to insert a new interval first, then merge? (stress-tests: pre-existing intervals) Insert the new interval in sorted position, then merge. Or: process in three phases: before overlap, during overlap (merge), after overlap. Connects to LC 57 Insert Interval.
   2. What if you needed the minimum removals to make all intervals non-overlapping? (stress-tests: merge vs remove) Sort by END time (not start), greedily keep the interval that ends earliest. Count = total - kept. Connects to LC 435 Non-overlapping Intervals. This is the activity selection problem.
   3. What if intervals were 2D (rectangles)? (stress-tests: 1D intervals) Sweep line: project onto one axis, handle events (rectangle starts/ends) along the perpendicular axis. Much more complex.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Merge Intervals generated via batch canonical enrichment pass. Review against personal solving experience and adjust.
   

2. Insert Interval (57) First we have to find the insertion point (use binary search) then we have to possibly merge the rest in a cascade (maybe).

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

   from bisect import bisect_left class Solution: def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]: # Find the insertion index for newInterval's start using bisect (log n) insert_idx = bisect_left(intervals, newInterval) intervals.insert(insert_idx, newInterval) # Now merge intervals as in the classic "merge intervals" pattern merged = [] start, end = intervals[0] for next_start, next_end in intervals[1:]: # If intervals overlap, extend the current interval's end if next_start <= end: end = max(end, next_end) else: # No overlap, add current and move to the next merged.append([start, end]) start, end = next_start, next_end # Don't forget the last interval merged.append([start, end]) return merged

   Code Snippet 2: Insert Interval (57)
   Pattern Extraction

   Core Insight: Process in three phases: intervals entirely before the new one (no overlap, add directly), intervals overlapping the new one (merge by extending), intervals entirely after (add directly). The merge phase updates the new interval’s bounds. Pattern Name: Three-Phase Interval Insertion Canonical Section: Intervals > Overlap Resolution Recognition Signals:

   • “Insert a new interval into a sorted, non-overlapping list and merge”
   • Intervals are already sorted and non-overlapping
   • Single insertion + merge

   Anti-Signals:

   • Intervals are not sorted – sort first, then merge all (LC 56)
   • Multiple insertions – batch insert then merge, or use an interval tree

   Decision Point: Insert = three-phase scan. Merge all = sort by start then sweep (LC 56). The pre-sorted, non-overlapping input is what enables the three-phase approach.

   Pitfalls and Misconceptions

   1. Trap: Sorting the intervals after adding the new one and then merging. Why: Works but is \(O(n \log n)\). The three-phase approach is \(O(n)\) because the input is already sorted. Correction: Scan linearly: before-overlap, during-overlap (merge), after-overlap.
   2. Trap: Getting the overlap condition wrong. Why: An interval [a, b] overlaps with [c, d] iff a < d AND c <= b=. Getting the direction wrong misses overlaps or incorrectly merges non-overlapping intervals. Correction: Phase 1: intervals[i][1] < newInterval[0] (entirely before). Phase 2: intervals[i][0] < newInterval[1]= (overlaps). Phase 3: everything else.
   Problem Mutations

   1. What if you needed to merge ALL overlapping intervals (not just insert one)? (stress-tests: single insertion) Sort by start, sweep and merge. This IS LC 56 Merge Intervals.
   2. What if insertions were frequent (online)? (stress-tests: single insertion) Use an interval tree for \(O(\log n)\) insertion with automatic overlap detection.
   3. What if you needed to delete an interval instead of insert? (stress-tests: insertion vs deletion) Find and remove the overlapping portion. May split one interval into two.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Insert Interval generated via batch canonical enrichment pass.
   

Non-Overlapping & Erasing Intervals #

• Maximum number of non-overlapping intervals or minimum removals

Problems #

1. Non-overlapping Intervals (435)

   Complements Approach: Number of intervals to remove to get number of non-overlapping intervals = total number of intervals - number of non overlapping intervals. To calculate the number of non overlapping intervals, we keep an accumulator end timing for the safe intervals only.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

   class Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: # trivial early returns: if not intervals: return 0 # remember to sort by end time: intervals.sort(key= lambda x: x[1]) count_non_overlapping = 1 prev_accepted_end = intervals[0][1] for start, end in intervals[1:]: # not overlapping: if start >= prev_accepted_end: count_non_overlapping += 1 prev_accepted_end = end # We don’t update last_end when there’s an overlap because: # - The intervals are sorted by their end times in ascending order. # - This means the previously chosen interval (`last_end`) always ends *earlier* or *at the same time* as the current overlapping interval. # - So, among overlapping intervals, the chosen one is guaranteed to have the earliest end time, minimizing future conflicts. # - Thus, when an overlap occurs, we skip the current interval and continue using the previous interval’s end (`last_end`) as our reference. return len(intervals) - count_non_overlapping

   Code Snippet 3: Non-overlapping Intervals (435) – complements approach

   The non-complement approach is more explicitly greedy. At each step when we find a colliding interval, we keep the one that has the least likelihood of a future collision (so ends the earliest).

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

   class Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: # trivial early returns: if not intervals: return 0 # remember to sort by end time: intervals.sort(key= lambda x: x[1]) t_start, t_end = intervals[0] count = 0 for start, end in intervals[1:]: # case 1: no collision: if start >= t_end: t_start, t_end = start, end # case 2: have collision: else: # removal case: # we pick the one that will have the least likelihood of future collision and increment the counter # if current interval ends earlier, keep it, rm target if end < t_end: t_start, t_end = start, end count += 1 else: # the target works, just keep that going count += 1 return count

   Code Snippet 4: Non-overlapping Intervals (435) – NOT the complements approach
   Here’s how the greedy framework has been applied

   1. having a frameworked-approach to this thinking:

   2. Problem Identification \(\implies\) there’s a min/max-ing going on We want to minimize the number of intervals to remove so that no two intervals overlap.

      Equivalently, maximize the number of intervals you keep with no overlaps.

   3. Greedy Choice Property \(\implies\) pick the interval with earliest finishing to max the remaining timeslots for others

      Among intervals that you could include next, the greedy choice is to pick the interval with the earliest finishing time (smallest end time).

      This is because picking the earliest finishing interval maximizes the remaining “free” timeline for others.

      This greedy choice is indeed part of some globally optimal solution (this can be rigorously proved).

   4. Optimal Substructure \(\implies\) reduces to a smaller subproblem

      If you choose the earliest finishing interval I1, then the problem reduces to:

      “Choose non-overlapping intervals from those starting after I1 ends”, which is a smaller subproblem.

      The optimal solution to the original problem contains the optimal solution to this smaller (sub)problem.

   5. Candidate Greedy Strategies Considered

      Earliest start time — bad, might block timeline with long intervals ending late.

      Shortest duration — also less effective, can still cause overlap.

      Least overlap count — complex to compute and no greedy shortcut.

      Earliest finishing time — best candidate for maximizing non-overlapping intervals.

   6. Proof of Correctness (Sketch)

      Greedy stays ahead: At each step, your greedy solution ends intervals earlier or equal compared to any other optimal solution, allowing at least as many intervals to fit afterward.

      Exchange argument: Any optimal solution can be rearranged to pick the earliest finishing interval first without reducing the total number of intervals selected.

   7. Design and Implementation

      • Sort intervals ascending by end time.

      • Initialize count of selected intervals = 1 (for first interval).

      • Set last_end = end time of first interval.

      • For each next interval:

        • If start > last_end=, select it and update last_end.

        • Else, skip/removal required.

      Result = total intervals - count selected.

   Pattern Extraction

   Core Insight: Sort by END time. Greedily keep intervals that end earliest (activity selection). Count = total - kept. This minimises removals because early-ending intervals leave the most room for future ones. Pattern Name: Activity Selection / Greedy Interval Scheduling Canonical Section: Intervals > Interval Scheduling Recognition Signals:

   • “Minimum removals to make all intervals non-overlapping”
   • Equivalent to “maximum number of non-overlapping intervals” (complement)
   • Sort by END time (not start time)

   Anti-Signals:

   • Sort by start time – that’s for merging (LC 56), not scheduling
   • Need to MERGE overlapping intervals – different problem, different sort key
   • Weighted intervals (different values) – DP, not greedy. Connects to weighted job scheduling

   Decision Point: Merging = sort by start. Scheduling (max non-overlapping) = sort by end. The sort key is the critical distinction.

   Pitfalls and Misconceptions

   1. Trap: Sorting by start time instead of end time. Why: Sorting by start time doesn’t give the greedy property. An interval starting early but ending late blocks many future intervals. Correction: Sort by interval[1] (end time). Keep the interval that ends earliest.
   2. Trap: Counting the intervals to KEEP instead of to REMOVE (or vice versa). Why: The problem asks for minimum removals. The greedy finds maximum kept. removals = n - kept. Correction: Track kept count. Return n - kept.
   Problem Mutations

   1. What if each interval had a weight and you wanted maximum weight non-overlapping set? (stress-tests: unweighted) Greedy doesn’t work with weights. Use DP: sort by end time, binary search for the last non-overlapping interval. \(O(n \log n)\). This is the weighted job scheduling problem.
   2. What if you needed to find the minimum number of rooms (not removals)? (stress-tests: problem framing) Count maximum simultaneous overlaps. That’s LC 253 Meeting Rooms II. Different problem entirely.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Non-overlapping Intervals generated via batch canonical enrichment pass.
   

Meeting Rooms / Scheduling #

• Meeting room allocation and finding minimal room count

Problems #

1. Meeting Rooms I (LC 252, NC)

   This is essentially a merge intervals style question

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   class Solution: def canAttendMeetings(self, intervals: List[Interval]) -> bool: if not intervals: return True intervals.sort(key=lambda x: x.start) prev_end = intervals[0].end for interval in intervals[1:]: if interval.start < prev_end: # Overlap detected return False prev_end = interval.end return True

   Code Snippet 5: LC
   Pattern Extraction

   Core Insight: Sort intervals by start time. If any interval’s start is before the previous interval’s end, there’s a conflict. Pattern Name: Sorted Overlap Detection Canonical Section: Intervals > Overlap Detection Recognition Signals:

   • “Can a person attend all meetings?” = “are any meetings overlapping?”
   • Sort + scan for adjacent overlap

   Anti-Signals:

   • Need minimum rooms – that’s Meeting Rooms II (LC 253)

   Decision Point: Boolean overlap detection = sort + check adjacent pairs. Counting overlaps = sweep line or heap.

   Pitfalls and Misconceptions

   1. Trap: Checking ALL pairs instead of just adjacent (after sorting). Why: After sorting by start time, if interval \(i\) doesn’t overlap \(i-1\), it can’t overlap any earlier interval either. Correction: Sort by start, check intervals[i].start < intervals[i-1].end for adjacent pairs.
   Problem Mutations

   1. What if you needed minimum rooms? (stress-tests: boolean overlap) Heap or event counting. Connects to LC 253.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Meeting Rooms I.
   

2. Meeting Rooms II (253) (NC link)

   We have 2 choices: we can use a min heap and play with the intervals OR we can do the sweep line algo Here’s my version with PQs:

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

   import heapq class Solution: def minMeetingRooms(self, intervals: List[Interval]) -> int: if not intervals: return 0 # Sort intervals by start time intervals.sort(key=lambda x: x.start) # Min-heap to track end times of meetings currently occupying rooms min_heap = [] # Add the first meeting's end time heapq.heappush(min_heap, intervals[0].end) for interval in intervals[1:]: start, end = interval.start, interval.end # If the current meeting starts after or when a room is freed if start >= min_heap[0]: heapq.heappop(min_heap) # Reuse room # Assign new room (or reused room with updated end time) heapq.heappush(min_heap, end) # Number of rooms = size of min-heap return len(min_heap)

   Code Snippet 6: Meeting Rooms II (253)

   And here’s the usage of the sweep line algo

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

   # SWEEP-LINE ALGO def minMeetingRooms(intervals): if not intervals: return 0 starts = sorted(i[0] for i in intervals) ends = sorted(i[1] for i in intervals) s, e = 0, 0 rooms = 0 max_rooms = 0 while s < len(intervals): if starts[s] < ends[e]: rooms += 1 max_rooms = max(max_rooms, rooms) s += 1 else: rooms -= 1 e += 1 return max_rooms # - Explanation: # - Separate all start times and end times into two sorted lists. # - Use pointers to iterate through both arrays, increment a counter when a meeting starts, decrement when one ends. # - Track the max counter during traversal → max concurrency → min rooms required. # - This approach avoids heaps and uses two sorted arrays, can be slightly faster for certain use-cases.

TODO Maximum Coverage & Sweep Line #

• Use line sweep algorithms or segment trees for calculating coverage, overlapping sums, or event counts

Problems #

1. My Calendar III (732)
2. Employee Free Time (759)

TODO Interval Partitioning & Coloring #

• Partition intervals into minimum number of sets so that intervals in each set do not overlap

Problems #

1. Interval Partitioning variants in scheduling
2. Coloring intervals to avoid conflicts (conceptual problems)

TODO Weighted Interval Scheduling / DP Variants #

• Maximize sum of weights of non-overlapping intervals using dynamic programming on sorted intervals

Problems #

1. Weighted interval scheduling classic problem (not always on LeetCode but often found in courses)

TODO K-Interval Combos & Sliding Window on Intervals #

• Problems requiring selection or counting of k intervals with certain properties or overlapping windows

Problems #

1. Subarray with k intervals meeting sum/coverage thresholds (advanced/hybrid problems)

TODO Circular Intervals / Wrap-Around Problems #

• Intervals defined on circular structures (e.g., circular calendar, clock wraps)

Problems #

1. Maximum Sum Circular Subarray (918) (conceptual overlap)

Interval Queries and Updates (Segment Tree / BIT applications) #

• Support dynamic queries and updates on interval data (sum, min, max)

Problems #

1. Range Sum Query data structure questions This is a whole category of its own, wherein we need to be able to maintain range sums, allowing efficient querying and updating.

   Here are some problems:

   • Number of Integers with Popcount-Depth Equal to K II (3624) The key idea here is that we need to accumulate interval counts of the popcount depths for depths in range [0, 5], so we have 6 different fenwick trees to track this. Querying comes in 2 forms: range queries and update queries and both can be handled in \(O(log n)\) time thanks to the use of fenwick trees.
   • Online interval aggregation and updates (advanced applications)
   • Minimum Interval to Include Each Query (1851) this is a greedy approach. Intervals sorted by start time ensure a one-way arrival order. Queries sorted by value ensure linear iteration. Heap keeps track of “active” intervals that could possibly cover the current query, always allowing quick retrieval of smallest size interval for coverage.

     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

     import heapq from typing import List, Tuple class Solution: def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]: # Sort intervals by start time ascending intervals.sort(key=lambda x: x[0]) # Pair queries with indices, then sort by query value sorted_queries = sorted((q, idx) for idx, q in enumerate(queries)) res = [-1] * len(queries) # Default to -1 (no interval found) min_heap = [] i = 0 # Pointer for intervals for query, idx in sorted_queries: # Push all intervals starting <= query into heap while i < len(intervals) and intervals[i][0] <= query: start, end = intervals[i] size = end - start + 1 heapq.heappush(min_heap, (size, end)) i += 1 # Remove intervals from heap that do NOT cover query (end < query) while min_heap and min_heap[0][1] < query: heapq.heappop(min_heap) # After cleanup, top heap element (if exists) is smallest interval covering query if min_heap: res[idx] = min_heap[0][0] return res

     Code Snippet 7: Minimum Interval to Include Each Query (1851)

Multi-Dimensional Interval Problems #

• Interval extensions in 2D or higher (rectangles, cuboids) involving overlapping area, union etc.

TODO Problems #

1. Skyline problem variants
2. Maximum Rectangle in Histogram (conceptually interval-based)

SOE #

• If using a temp accumulator, forgetting to add that in at the last step is a common error. For example, in insert intervals:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

  from bisect import bisect_left class Solution: def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]: # Find the insertion index for newInterval's start using bisect (log n) insert_idx = bisect_left(intervals, newInterval) intervals.insert(insert_idx, newInterval) # Now merge intervals as in the classic "merge intervals" pattern merged = [] start, end = intervals[0] for next_start, next_end in intervals[1:]: # If intervals overlap, extend the current interval's end if next_start <= end: end = max(end, next_end) else: # No overlap, add current and move to the next merged.append([start, end]) start, end = next_start, next_end # Don't forget the last interval merged.append([start, end]) return merged

  Code Snippet 8: TODO Problems
• Sorting by wrong key (start vs end)
• Incorrect handling of equal endpoint intervals
• Off-by-one errors in boundary conditions
• REMEMBER that only overlaps matter so if they kiss at the ends, it’s alright

Greedy Choice Validation #

• Applying greedy without verifying the greedy choice property holds. Many problems LOOK greedy but require DP (e.g., coin change with arbitrary denominations). If a counterexample to the greedy choice exists, the approach is wrong.
• Wrong sorting key: sorting by start time when end time is needed (activity selection), or vice versa. The choice of sorting key IS the greedy decision.

Exchange Argument Failures #

• Failing to recognise when a greedy swap would improve the solution: if swapping two adjacent elements in any proposed optimal solution can improve or maintain optimality, the greedy choice is valid. Failure to construct this argument means the greedy approach might be wrong.

Greedy with Constraints #

• Greedy works well when constraints are simple (one dimension). When constraints are multi-dimensional (weight AND value), greedy typically fails and DP is needed. The anti-signal is: “would sorting by one criterion leave the other unconstrained?”

Decision Flow #

• Overlap resolution? -> Sort by start / end + greedy merge
• Scheduling / resource allocation? -> Sweep line or priority queue
• Need min rooms/resources? -> Sort by start + min-heap of end times, or sweep line
• Need to answer point queries over intervals? -> Sort intervals + binary search or segment tree
• Dynamic interval queries? -> Segment tree or balanced tree
• Since space optimisation is something to consider, sometimes, we’re concerned with an order statistic instead of the actual configuration / sequence => consider DP over other approaches (like backtracking).

Styles, Tricks and Boilerplate #

1. TRICK: simpler overlap test: use the complement

   • To check if the two regions \([a, b]\) and \([c, d]\) overlap,

     Check their complement!

     They would NOT overlap if \(b < c\) or \(d < a\).

     So the complement to that would be: \(\not ((b < c) \lor (d < a))\)

     Therefore, here’s what we should be doing:

     ​          - is_overlapping = (t_start <= start <= t_end) or (t_start <= end <= t_end) or (start <= t_start <= end) or (start <= t_end <= end)
     ​          + is_overlapping = not (end < t_start or t_end < start)

Boilerplate #

Interval Merge #

1
2
3
4
5
6
7
8
9

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

Sweep Line for Max Concurrency #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def max_concurrency(intervals):
    events = []
    for start, end in intervals:
        events.append((start, 1))   # meeting starts
        events.append((end, -1))    # meeting ends
    events.sort()

    max_overlap = current = 0
    for _, delta in events:
        current += delta
        max_overlap = max(max_overlap, current)
    return max_overlap

TODO KIV #