Unlike the Interval Scheduling Problem where we sought to maximize the number of requests that could be accommodated simultaneously, in the Weighted Interval Scheduling Problem, each request i has an associated value or weight w_{i} and the goal is to find the maximum-weight subset of compatible requests. It degenerates to the interval scheduling problem when w_{i} = 1 ∀i.

No greedy algorithm is known to solve this problem optimally. However, it can be solved with dynamic programming.

Suppose the requests are sorted in order of non-decreasing finish time: f_{1} ≤ f_{2} ≤ … ≤ f_{n}. This defines a natural ordering of requests. Let p(j), for an interval j, be the largest i < j s.t. the intervals i and j are disjoint i.e., i is the interval having the greatest finish time f_{i} s.t. f_{i} ≤ s_{j}.

Let there be an optimal solution O. Either an interval i belongs to O or it doesn’t. If i ∈ O, then no interval strictly between p(i) and i could belong to O. Moreover, if i ∈ O, then O must include an optimal solution consisting of requests {1, 2, …, p(i)} because if it did not, we could replace O’s choice of requests from {1,2,…,p(i)} with a better one without any danger of overlapping request i. If i ∉ O, then O is simply the optimal solution to the problem consisting of requests {1, 2, …, i-1}.

For 1 ≤ j ≤ n, let O_{j} denote the optimal solution to the problem consisting of requests {1, 2, …, j} and OPT(j) denote the value of this solution, then we have the following recursive formulation:

OPT(j) = max(w_{j} + OPT(p(j)), OPT(j-1))

**Recursive formulation:**

However, implementing it directly would take exponential time but there are only a linear number of subproblems O(j) for j in {1, 2, …, n} so by memoizing results or computing the results bottom-up, we can reduce the running time to a polynomial.

**Algorithm:**

- Sort the requests in order of non-decreasing finish times. This step takes time O(n log n).
- For 1 ≤ j ≤ n, find the largest i < j s.t. f
_{i}≤ s_{j}, call it p(j). Since the requests are sorted in order of non-decreasing finish times, we can use binary search to find p(j) in time O(log j). Thus, this step takes time sum(O(log j)) for 1 ≤ j ≤ n = O(n log n). - For 1 ≤ j ≤ n, compute OPT(j) = max(w
_{j}+ OPT(p(j)), OPT(j-1)). This step takes time O(n).

Thus the overall time complexity of the algorithm is O(n log n).

Take a look at C++ implementation.

**Reference:** Algorithm Design by Kleinberg and Tardos

how do you pick final scheduled intervals in the end?How to get the optimal solution ?

Once we have precomputed the values of OPT[1..n], we can use the recursive formulation (OPT(j) = max(wj + OPT(p(j)), OPT(j-1))) to traverse OPT array from the last to get the optimal solution.

Starting at j = n, if w[j] + OPT[p[j]] >= OPT[j-1], we include interval j in the final solution and move j to p[j], otherwise we move j to j-1. Take a look at the code: https://github.com/kartikkukreja/blog-codes/blob/master/src/Weighted%20Interval%20Scheduling%20Problem.cpp