---
# System prepended metadata

title: ADA 6.2 Weighted Interval Scheduling
tags: [ADA 6.2]

---

###### 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

![](https://i.imgur.com/VHog9T1.png)

:::danger
![](https://i.imgur.com/WW3krnD.png)

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.

![](https://i.imgur.com/fKCItm6.png)
