2
$\begingroup$

Suppose I have set of time records as follows

08:00 - 12:00
10:00 - 12:00
08:00 - 13:00
13:00 - 19:00
12:00 - 17:00

Now I want to select set of time records that are not overlapping and has the largest sum.

 08:00 - 13:00 + 13:00 - 19:00 = 12hours

My current approach is

  1. Sort the records by start time
  2. Select the first record and compare with each record and get the sum and store sum and the index of records.
  3. Then select the second item repeat the process.
  4. Loop through sum array and find the largest sum and indexes of records

Is there any better approach I can follow ? Is this a problem related to Dynamic programming ?

Thanks.

$\endgroup$
1
$\begingroup$

Your problem is known as weighted interval scheduling, and can be solved using dynamic programming. It's a nice exercise. You can find the solution in these lecture notes as well as in many other places.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.