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
- Sort the records by start time
- Select the first record and compare with each record and get the sum and store sum and the index of records.
- Then select the second item repeat the process.
- 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 ?