Interval Scheduling

Problem

Given intervals as [start, end] pairs, return the maximum number of mutually non-overlapping intervals that can be selected.

Use the greedy earliest-finish-first rule: sort by end time, then always take an interval whose start is at least the end of the last chosen interval. Intervals that only touch at an endpoint are considered compatible.

Hint

Choosing the interval that finishes earliest leaves the most room for the rest.

Test cases

case 1

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

expected: 2

case 2

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

expected: 3

case 3

in: [[]]

expected: 0

case 4

in: [[[1,5]]]

expected: 1

case 5

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

expected: 2

Starter codePython

def max_non_overlapping(intervals):
    # Your code here
    pass

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