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:

A framework of thought for Greedy Algos

Formal Framework for Understanding and Applying Greedy Algorithms

Here’s a step-by-step template/framework for analyzing and designing greedy algorithms:

Problem Identification:
- Does the problem ask for an optimal subset or sequence?
- Are you trying to maximize/minimize something subject to constraints?
Greedy Choice Property:
- Can you make a locally optimal choice at each step that is part of some global optimal solution?
- Example greedy choices could be earliest finishing time, shortest duration, smallest cost, etc.
Optimal Substructure:
- Does the problem exhibit optimal substructure?
- That is, does an optimal solution to the problem contain optimal solutions to subproblems?
Candidate Greedy Strategies:
- List out all possible “greedy” choices you might try (e.g., earliest start, earliest finish, shortest length).
- Test how intuitive or promising each strategy looks with small examples.
Proof or Intuition of Correctness:
- Use “Greedy stays ahead” or “Exchange argument” proof techniques to argue your greedy choice leads to optimal solution.
- Greedy stays ahead: show your greedy algorithm is never worse than any other solution at each step.
- Exchange argument: show that any optimal solution can be converted to your greedy one without loss.
Design and Implementation:
- Implement your approach carefully.
- Usually involves sorting based on greedy criteria.
- Iterate through candidates, making decisions based on the greedy choice.
Analyze Complexity:
- Time complexity will often involve sorting (\(O(n log n)\)) plus linear scan.
- Space complexity is often \(O(1)\) or \(O(n)\).

Canonical Question Types #

Merge & Insert Intervals #

Merge overlapping intervals, insert new interval maintaining order

Problems #

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

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

Non-Overlapping & Erasing Intervals #

Maximum number of non-overlapping intervals or minimum removals
Problems:

Problems #

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

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

Here’s how the greedy framework has been applied

having a frameworked-approach to this thinking:
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.
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).
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.
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.
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.
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.

Meeting Rooms / Scheduling #

Meeting room allocation and finding minimal room count

Problems #

Meeting Rooms I (LC, 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

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)

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 #

TODO Interval Partitioning & Coloring #

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

Problems #

Interval Partitioning variants in scheduling
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 #

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 #

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 #

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 #

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.

 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
33
34
35
36
37
38

        - Online interval aggregation and updates (advanced applications)
​        - [[https://leetcode.com/problems/minimum-interval-to-include-each-query/][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.
          #+begin_src python -n
      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

Multi-Dimensional Interval Problems #

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

TODO Problems #

Skyline problem variants
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

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

Decision Flow #

Overlap resolution? → Sort by start / end + greedy merge
Scheduling / resource allocation? → Sweep line or priority queue
Dynamic interval queries? → Segment tree or balanced tree

Styles, Tricks and Boilerplates #

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)
```