Weighted Interval Scheduling

Problem

Given intervals as [start, end, weight] triples, return the maximum total weight of a set of mutually non-overlapping intervals.

Sort by end time and let dp[i] be the best using the first i intervals; for each interval find the last compatible earlier interval and choose between skipping or taking it. Touching endpoints are compatible.

Hint

j is the number of intervals that end at or before the current start.

Test cases

case 1

in: [[[1,3,5],[2,5,6],[4,6,5],[6,7,4],[5,8,11],[7,9,2]]]

expected: 17

case 2

in: [[]]

expected: 0

case 3

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

expected: 3

case 4

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

expected: 10

case 5

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

expected: 12

Starter codePython

def weighted_interval_scheduling(intervals):
    # Your code here
    pass

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