Weighted Interval Scheduling

want to maxmize weight by scheduling

Greedy no longer works

Dynamic Programming

define the subproblem == Rx 

R == nubmer of request , x == f(i) finishing time , Rf(i) ~= request later than f(i)

Rx = {j ∈ R|s(j) ≥ x} given particular x i can always shrink nubmer of request that i have based on {s(j} >=x} (rule)

Dp guessing

Try each request i as a possible First Solution  // 

try everything as first solution and look for opt(Rf(i)) if it is duplicate where Rf(i) is set of request that satsify s(i) >f(i) , starting time is later than finishing time

n subproblems * subproblem takes max O(n) == O(n^2)

Make it better~ where is the inefficency?

1. repeating solving subproblems ,  we need to memoize subproblem's result so we can reuse.

2. we shouldn't try every request some request is more suitable to be first

opt(1,2,3...n) == max(opt(2,...n) , w1 + opt(R1))

opt(2..n) == not choosing first request to be my first solution 

w1 + opt(R1) == choosing first as my first solution + solving subproblem that satsify s(i) >f(1)

Time == sorting (nlong) + recusrsion (n) == nlogn

why above(first) algorthim's recursion O(n^2) not O(n)  

recursion tree , first algorithm has more branch (not just 2) whenever we go up in tree so 1+2+3+4+..n = O(n^2)

 

 

 

 

Non-identical machines (NP-complete)

machines  τ = {T1, . . . , Tm}.

this particular interval can only work on some subset of machine

Can k ≤ n requests be scheduled? (decision problem) k == specific number 

Reference == 

1. Course Overview, Interval Scheduling - YouTube

R1. Matrix Multiplication and the Master Theorem - YouTube