Bird
Raised Fist0
Interview PrepintervalsmediumFacebookAmazonGoogleMicrosoftBloomberg

Merge Intervals

Choose your preparation mode4 modes available
▶
Steps
setup

Check for empty input and sort intervals

The algorithm first checks if the input is empty. Then it sorts the intervals by their start times to prepare for merging.

💡 Sorting ensures intervals are in order, so overlapping intervals appear consecutively, simplifying merging.
Line:if not intervals: return [] intervals.sort(key=lambda x: x[0])
💡 Sorting is a crucial preprocessing step that enables linear merging.
📊
Merge Intervals - Watch the Algorithm Execute, Step by Step
Watching each pointer move and comparison helps you understand exactly how intervals are merged in-place without extra space.
Step 1/12
·Active fill★Answer cell
setup
0
1
2
3
setup
index
0
1
2
3
move_right
index
0
i
1
2
3
compare
index
0
i
1
2
3
insert
index
0
i
1
2
3
move_right
index
0
1
i
2
3
compare
index
0
1
i
2
3
insert
0
index
1
i
2
3
move_right
0
index
1
2
i
3
compare
0
index
1
2
i
3
insert
0
1
index
2
i
3
record
0
1
index
2
3
Result: [[1,6],[8,10],[15,18]]

Key Takeaways

✓ Sorting intervals by start time is essential to enable linear merging.

Without sorting, overlapping intervals could be scattered, making merging complex.

✓ The 'index' pointer tracks the last merged interval, allowing in-place merging without extra space.

This pointer movement shows how the algorithm compacts merged intervals at the front.

✓ Overlapping intervals are merged by extending the end time, while non-overlapping intervals advance the 'index' and are copied.

Seeing this decision visually clarifies when intervals combine versus when a new merged interval starts.

Practice

(1/5)
1. Given two lists of closed intervals, each sorted and non-overlapping within themselves, you need to find all intervals where the two lists overlap. Which approach guarantees an optimal time complexity solution?
easy
A. Use a brute force nested loop to compare every interval in the first list with every interval in the second list.
B. Use two pointers to traverse both lists simultaneously, advancing the pointer with the smaller interval endpoint to find intersections efficiently.
C. Sort all intervals from both lists together and then merge overlapping intervals to find intersections.
D. Use dynamic programming to store and compute overlapping intervals between the two lists.

Solution

  1. Step 1: Understand problem constraints

    Both lists are sorted and non-overlapping internally, so a linear scan is possible.
  2. Step 2: Identify the optimal approach

    Two pointers allow simultaneous traversal, comparing intervals in O(m + n) time, advancing pointers based on interval endpoints.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Two pointers avoid unnecessary comparisons and achieve linear time [OK]
Hint: Two pointers exploit sorted order for linear time [OK]
Common Mistakes:
  • Assuming brute force is acceptable
  • Thinking sorting combined lists is needed
  • Misapplying DP to interval intersection
2. You are given a list of intervals where each interval has a start and end time. Your goal is to select the maximum number of intervals such that none of the selected intervals overlap. Which algorithmic approach guarantees an optimal solution for this problem?
easy
A. Dynamic programming that tries all subsets of intervals to find the maximum non-overlapping set.
B. Sort intervals by their start time and always pick the earliest starting interval first.
C. Sort intervals by their end time and greedily select intervals that start after the last selected interval ends.
D. Use a graph coloring algorithm to assign intervals to different colors ensuring no overlaps.

Solution

  1. Step 1: Understand the problem goal

    The problem requires selecting the maximum number of intervals with no overlaps.
  2. Step 2: Identify the optimal greedy strategy

    Sorting intervals by their end time and greedily picking intervals that start after the last selected interval ends ensures the maximum number of intervals are chosen.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Greedy by earliest end time is a classic optimal approach [OK]
Hint: Sort by end time for max non-overlapping intervals [OK]
Common Mistakes:
  • Sorting by start time and picking earliest start first
  • Trying brute force DP without pruning
  • Using graph coloring which is unrelated here
3. Examine the following buggy code for the Meeting Rooms II problem. Which line contains the subtle bug that can cause incorrect room count?
medium
A. Line 3: Missing check for empty intervals list.
B. Line 9: Incorrect condition using >= instead of > for overlap.
C. Line 11: Using heappush without popping first.
D. Line 6: Intervals are not sorted before processing.

Solution

  1. Step 1: Identify missing sorting.

    Intervals must be sorted by start time before heap processing; missing this breaks heap logic.
  2. Step 2: Confirm other lines.

    Empty check is present; condition >= is correct for allowing room reuse; pushing after popping is correct.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Without sorting, heap logic fails to track earliest ending meeting [OK]
Hint: Heap logic requires sorted intervals by start time [OK]
Common Mistakes:
  • Confusing overlap condition with <=
  • Forgetting to sort intervals
  • Misordering heap push/pop
4. If employees can have intervals with negative start or end times (e.g., [-5, 0]) or zero-length intervals, which modification to the sweep line algorithm is necessary to correctly find free time?
hard
A. Ignore zero-length intervals and ensure sorting places end events before start events at ties
B. Treat zero-length intervals as free time intervals
C. Sort events only by time, ignoring event type
D. Merge touching intervals as free time gaps

Solution

  1. Step 1: Handle zero-length intervals

    Zero-length intervals like [2,2] do not represent busy time and should be ignored to avoid false free intervals.
  2. Step 2: Maintain correct sorting order

    Sorting end events before start events at same time prevents reporting free time between touching intervals or zero-length intervals.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Ignoring zero-length intervals and correct sorting avoids invalid free times [OK]
Hint: Ignore zero-length intervals and sort end before start events [OK]
Common Mistakes:
  • Counting zero-length intervals as free time
  • Sorting start before end events
5. Suppose intervals can have negative values and zero length (start == end). Which modification to the optimal solution is necessary to correctly remove covered intervals?
hard
A. Change sorting to (start ascending, end ascending) to handle zero-length intervals correctly.
B. Use strict inequality 'if end > max_end' to avoid counting zero-length intervals as uncovered.
C. Switch to brute force nested loops to handle negative and zero-length intervals safely.
D. Keep sorting by (start ascending, end descending) and use 'if end >= max_end' to include zero-length coverage cases.

Solution

  1. Step 1: Consider zero-length intervals

    Zero-length intervals (start == end) require coverage detection to include intervals with equal ends.
  2. Step 2: Adjust inequality and sorting

    Sorting by start ascending and end descending remains correct; change condition to 'if end >= max_end' to count intervals not strictly greater but equal ends.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Using >= includes zero-length coverage correctly without changing sorting [OK]
Hint: Use >= in condition to handle zero-length intervals [OK]
Common Mistakes:
  • Changing sorting breaks coverage detection
  • Using strict > misses zero-length coverage
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard