$O(n^2)$ Dynamic Programming (Weighted Activity Selection Problem Interval Scheduling)

From Algorithm Wiki

Jump to navigation Jump to search

Time Complexity

$O(n^{2})$

Space Complexity

$O(n)$ words

(Keep track of answers to O(n) subproblems (cache), and sorted list of intervals)

Description

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

1953

Reference

Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=$O(n%5E2)$_Dynamic_Programming_(Weighted_Activity_Selection_Problem_Interval_Scheduling)&oldid=45587"