###### tags: `ADA 6.2`

# ADA 6.2 Weighted Interval Scheduling
> Sorry, I do not finish watching the video which content is too empty for me.

:::info
I recommend the pdf linked below.
[Reference pdf](https://courses.cs.washington.edu/courses/cse521/13wi/slides/06dp-sched.pdf)
:::

## Question
Find the most valuable combination in which time does not overlap.

### Inpput
- Jobs
- Time to begin and finish
- Values


:::danger

Recursive algorithm fails spectacularly because of redundant sub-problems ⇒ exponential algorithms.
$$\sum^{n}_{i=1} n(n-1) / 2$$
:::

### Soultion

1. Sort the job by time.
2. Create a iterator to filter all of items of next step. P(n)
3. Create a computer the max value for per step by dynamic programming.