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.

+3


source to share





All Articles