Introduction
How do you use this website?
DPMediumMath
Math Test
If KaTeX is working, this should render as a properly formatted fraction:
Interactive Templates
Here are the custom components you can use in your editorials:
Key Observation
The problem reduces to finding the longest path in a Directed Acyclic Graph (DAG). Once we sort the nodes topologically, we can compute the longest path in time!
Reveal Hint▼
Have you considered sorting the intervals by their end time before applying greedy selection?
Time ComplexityO(N log N)
Space ComplexityO(N)
Visualizations
0
4
1
2
2
7
3
1
4
9
5
3
A
BC
B
D
C
DE
D
empty
E
A
| w=0 | w=1 | w=2 | w=3 | |
|---|---|---|---|---|
| i=0 | 0 | 0 | 0 | 0 |
| i=1 | 0 | 3 | 3 | 3 |
| i=2 | 0 | 3 | 4 | 7 |