Non-Overlapping Intervals

Python data engineering interview problem. Difficulty: intermediate. Pattern: Intervals. About 14 minutes. Part of the Pro drill bank.

Minimum removals to make intervals non-overlapping. Treat this as a production helper: match the contracted return shape, including empty and duplicate inputs.

A scheduler wants to keep as many non-overlapping meetings as possible. Every interval removed is one job that cannot stay in the schedule. Return the minimum number of intervals to remove so that the intervals left do not overlap. Two intervals that meet at an endpoint are allowed to coexist in the shown contract. Write the function erase_overlap_intervals(intervals: list) -> int. For [[1, 2], [2, 3], [3, 4], [1, 3]], remove [1, 3] and keep the other three, so the answer is 1. The starter file already has the function name and the harness print lines. Keep them, and fill only the function body.

Requirements

• Keep the largest possible set of non-overlapping intervals.
• Return the number removed, not the intervals kept.
• Treat an end equal to the next start as non-overlapping.

Constraints

• Each interval has a start and end, and intervals may be unsorted.
• The return type is int; an empty or one-interval input needs no removal.

Examples

Input: erase_overlap_intervals([[1, 2], [2, 3], [3, 4], [1, 3]]) Output: 1 Remove [1,3].

Topics: lakebench, python, greedy, erase.

More Python interview questions · All interview problems · Learn data engineering