Non-overlapping Intervals

Problem

Given intervals as [start, end] pairs, return the minimum number of intervals to remove so that the rest do not overlap.

Sort by end time and greedily keep every interval that starts at or after the last kept end. The answer is the total count minus the number kept; touching endpoints are compatible.

Hint

Keeping intervals that finish earliest maximises how many survive.

Test cases

case 1

in: [[[1,2],[2,3],[3,4],[1,3]]]

expected: 1

case 2

in: [[[1,2],[1,2],[1,2]]]

expected: 2

case 3

in: [[[1,2],[2,3]]]

expected: 0

case 4

in: [[]]

expected: 0

case 5

in: [[[1,10],[2,3],[3,4]]]

expected: 1

Starter codePython

def min_remove_overlapping(intervals):
    # Your code here
    pass

5 test cases · run your code against them in the editor