Sort n lists without matches
(This is my first question, if I am doing something wrong, tell me :))
I have n lists whose elements have an integer attribute (unique for each list) and duration in seconds.
I have to sort these lists without any overlap of elements with the same attribute in time and optimize the total duration (the duration of the longest list in time).
If there is no alternative, the time span is inserted until the duration of the other list item expires.
I have developed an algorithm that selects an element from the longest in time, adding all the same attributes to each list
Example (edited): each element is represented as (int att, duration time)
List 1: (1,20) (2,13) (3,15)
List 2: (1,14) (2,20) (3,14)
Optimum sorting:
List 1: (1,20) (3,15) (Gap,1) (2,13) List 1 duration: 20+15+1+13 = 49
List 2: (3,16) (2,20) (1,14) List 2 duration: 16+20+14 = 50
Total time: MAX(49,50) = 50
My algorithm:
Sorting by duration to select candidates: 1 (20+14 = 34 seconds), 2 (13+20 = 33 seconds), 3 (15+14 = 29 secs)
Final sorting:
List 1: (1,20) (2,13) (3,15) List 1 duration: 20+13+15 = 48
List 2: (2,20) (1,14) (Gap,14) (3,16) List 2 duration: 20+14+14+16 = 64
Total time: MAX(48,64) = 64
Does anyone know of an algorithm that optimizes sorting?
If this is not very well expressed please let me know
Sorry for my English: _)
(Edited)
I found Thesis in Spanish presenting the problem and suggesting some solutions. This is a job scheduling issue as pointed out in the comment to AShelly.
source to share
No one has answered this question yet
Check out similar questions: