Interval Problems

1. Introduction

What are Interval Problems?

Interval Problems require organizing blocks of time (start and end times) on a 1D timeline. Common variants include:

Interval Scheduling (Activity Selection): Finding the maximum number of non-overlapping tasks you can complete.

Merge Intervals: Combining overlapping blocks into a single consolidated interval.

Insert Interval: Inserting a new block into a set of sorted non-overlapping intervals, merging if necessary.

Why study them?

These problems are extremely common in coding assessments. They test your ability to sort structures according to various criteria (start time vs. end time) and manage coordinate edge overlaps.

---

2. Mental Model: The Booking Desk

Imagine managing booking requests at a recording studio:

Merge (Start-Time Sort): If client A books 1:00 PM - 3:00 PM and client B books 2:00 PM - 5:00 PM, their sessions overlap. You must merge them into a single occupied block: 1:00 PM - 5:00 PM.

Maximize Schedule (End-Time Sort): If multiple clients request slots, you want to fit in as many as possible. To do this, you always pick the request that finishes earliest, leaving the maximum possible time remaining for subsequent sessions.

---

3. Core Algorithms & Implementations

1. Merge Intervals (LeetCode 56)

Sort intervals by start time.

Iterate through intervals. If the current interval's start time ≤ the end time of the last merged interval, they overlap. Merge them by updating the last merged interval's end time to max(last_merged.end, current.end).

Otherwise, append the current interval as a new non-overlapping block.

2. Activity Selection / Max Non-Overlapping (LeetCode 435 / 646)

Sort intervals by end time.

Keep track of the end time of the last selected activity. If a new activity's start time ≥ the last selected end time, select it and update the end time threshold.

---

4. Visualizing Merging & Scheduling

Merging overlapping intervals [[1, 3], [2, 6], [8, 10]]:

---

5. Real-World Examples

Calendar Invite Triaging: Auto-declining overlapping meeting requests if they conflict with an existing meeting.

Video Rendering Sequencers: Merging adjacent video track slices that share timestamps.

---

6. Interview Perspective

How Interviewers Ask This Topic

Interviewers test sorting selection logic:

"Explain why we sort by end-times for Activity Selection." -> Sorting by end-time is a greedy strategy. By choosing the activity that finishes first, we maximize the remaining time left for other activities, guaranteeing the optimal number of scheduled sessions.

"Solve Insert Interval (LeetCode 57)." -> Divide the array into three parts: intervals ending before the new interval starts, merged intervals overlapping with the new interval, and intervals starting after the new interval ends. This runs in O(N) time.

Common Mistakes

> 2. Off-by-one boundary checks: Using < instead of ≤ (or vice versa) for overlaps. If an interval ends at 3 and the next starts at 3, they do not overlap (start >= last_end).

---

7. Summary

Merge: Sort by start-time. Combine overlapping intervals: next.start <= last.end.

Schedule: Sort by end-time. Pick next if next.start >= last.end.

Complexity: O(N log N) time (sorting bottleneck), O(N) space.

---

8. Quiz

Question 1: If meeting intervals are [[1, 4], [2, 3]], and we merge them, what is the resulting interval?

Answer: [1, 4]. The second interval is entirely nested inside the first one. max(4, 3) = 4.

Question 2: Why does Activity Selection sort by end-times rather than start-times?

Answer: If we sort by start-times, an activity starting at 9:00 AM and ending at 9:00 PM would be selected first, preventing us from scheduling multiple shorter activities that run throughout the day.

Question 3: What is the time complexity of the Insert Interval algorithm if the input is already sorted?

Answer: O(N) time, as we can insert the new interval and merge overlaps in a single linear pass without re-sorting the entire array.

Question 4: True or False: If two intervals [1, 5] and [5, 10] share boundary 5, they are considered overlapping in 'Merge Intervals'.

Answer: False (usually). They touch at boundary 5 but do not overlap. However, check LeetCode problem specifications: standard definitions treat start <= last_end as overlapping, which would merge them into [1, 10].

Question 5: What is the space complexity of Merge Intervals?

Answer: O(N) space to store the results list of merged intervals.