Non overlapping Intervals

TIP103 Unit 9 Session 1 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 20-30 mins
• 🛠️ Topics: Greedy Algorithms, Intervals, Sorting

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Q: What counts as an overlap between two bookings?

  • A: Two intervals overlap if one starts before the other ends. Intervals that only touch at an endpoint, like [1, 2] and [2, 3], do NOT overlap — the room frees up exactly when the next booking begins.

• Q: What should the function return?

  • A: The minimum number of requests to cancel, not the remaining bookings themselves. Equivalently, cancel as few intervals as possible so that the ones left are pairwise non-overlapping.

• Q: Can duplicate requests appear in the list?

  • A: Yes. For example, [1, 2] may appear multiple times, and duplicates fully overlap each other, so all but one must be cancelled.

HAPPY CASE
Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1
Explanation: Cancelling [1, 3] leaves [1, 2], [2, 3], [3, 4], which do not overlap.

Input: intervals = [[1, 2], [2, 3]]
Output: 0
Explanation: The bookings only touch at time 2, so nothing needs to be cancelled.

EDGE CASE
Input: intervals = [[1, 2], [1, 2], [1, 2]]
Output: 2
Explanation: All three requests are identical, so two of them must be cancelled to keep just one.

Input: intervals = [[1, 100], [2, 3], [4, 5], [6, 7]]
Output: 1
Explanation: One long booking conflicts with all the short ones. Cancelling only [1, 100] is better than cancelling the three short bookings.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Interval Scheduling Problems, we can consider the following approaches:

• Greedy (Interval Scheduling Maximization): Sort intervals by end time and repeatedly keep the booking that ends earliest. Keeping the earliest-ending interval leaves the most room for future bookings, so the number of kept intervals is maximized and the number of cancellations is minimized.
• Sorting: Nearly every interval problem starts by sorting; here sorting by end time (rather than start time) is what makes the greedy choice safe.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Flip the question around: instead of counting cancellations directly, keep the maximum number of non-overlapping bookings and cancel everything else. Sort the intervals by end time. Walk through them, keeping an interval whenever it starts at or after the end of the last kept interval. The answer is the total number of intervals minus the number kept.

1) If the list is empty, return 0.
2) Sort `intervals` by end time.
3) Initialize `kept = 0` and `prev_end = -infinity` (end of the last kept booking).
4) For each interval [start, end] in sorted order:
   a) If `start >= prev_end`, the booking fits: increment `kept` and set `prev_end = end`.
   b) Otherwise it overlaps the last kept booking, so it will be cancelled — skip it.
5) Return `len(intervals) - kept`.

⚠️ Common Mistakes

• Sorting by start time instead of end time. A booking that starts early but runs long (like [1, 100]) can wrongly crowd out many short bookings.
• Treating touching endpoints as overlaps. Use start >= prev_end to keep an interval, not start > prev_end.
• Returning the number of intervals kept instead of the number cancelled.
• Forgetting to update prev_end when keeping an interval, which lets overlapping bookings slip through.

4: I-mplement

Implement the code to solve the algorithm.

def erase_overlap_intervals(intervals):
    if not intervals:
        return 0

    # Sort intervals by their end time
    intervals.sort(key=lambda interval: interval[1])

    kept = 0                  # Count of non-overlapping intervals we keep
    prev_end = float('-inf')  # End time of the last interval we kept

    for start, end in intervals:
        if start >= prev_end:
            # No overlap with the last kept interval, so keep this one
            kept += 1
            prev_end = end

    # Everything we did not keep must be cancelled
    return len(intervals) - kept

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input: intervals = 1, 2], [2, 3], [3, 4], [1, 3

  • Sorted by end time: 1, 2], [2, 3], [1, 3], [3, 4
  • Keep [1, 2] (kept = 1, prev_end = 2), keep [2, 3] since 2 >= 2 (kept = 2, prev_end = 3), skip [1, 3] since 1 < 3, keep [3, 4] since 3 >= 3 (kept = 3).
  • Output: 4 - 3 = 1

• Input: intervals = 1, 2], [1, 2], [1, 2

  • Keep the first [1, 2] (kept = 1, prev_end = 2); the other two start at 1 < 2, so both are skipped.
  • Output: 3 - 1 = 2

• Input: intervals = 1, 2], [2, 3

  • Keep [1, 2], then keep [2, 3] since 2 >= 2 (kept = 2).
  • Output: 2 - 2 = 0

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of intervals in the input list.

• Time Complexity: O(N log N) because sorting the intervals dominates; the single pass afterward is O(N).
• Space Complexity: O(1) extra space beyond the input, since we sort in place and track only kept and prev_end. (Python's sort itself may use O(N) auxiliary space internally.)