CODEWITHSUNDEEP
algorithmschedulingintervals
Mike
Mike

Reputation: 385

weighted interval problem with dynamic programming

I am dealing with a weighted interval problem. In the traditional formulation, we have we have a list {i_1, ..., i_n} of jobs with weights w_j. I found a pretty straightforward approach with example from the book "Algorithm Design" by Kleinberg and Tardos where Dynamic Programming that is based on initially sorting the intervals by finishing time (https://www.cs.princeton.edu/courses/archive/spr05/cos423/lectures/06dynamic-programming.pdf). The algorithm makes use of the concept p_j (predecessor) which is the largest job i non-conflicting with job j. In my specific case, however, I am dealing with a problem where there are are several jobs with the same finish time, so I would have several p_js. Because of that I am not sure how straightforward or appropriate would be this DP approach for my problem. Do you have any suggestion?

Upvotes: 0

Views: 119

Answers (1)

Yola
Yola

Reputation: 19023

Observe that you need to order jobs using <= not < operator:

enter image description here

For this formula it doesn't matter if you have several jobs with the same ending time.

enter image description here

p(j) is one with the largest index among jobs with the same finishing time.

Upvotes: 1

Related Questions