1

I have a set of events with start and end times. I want to render them as long boxes in a series of rows with no overlap, something like this

00:00    01:00    02:00    03:00    04:00    05:00    06:00    07:00    08:00
--|--------|--------|--------|--------|--------|--------|--------|--------|--
      AAAAAAAAAAAA  BBBBBB        CCCCCCCCCCCCCCCCCCCC       DDDDDDDDDDDD
--|--------|--------|--------|--------|--------|--------|--------|--------|--
         EEEEEEEEEEEEEE      FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
--|--------|--------|--------|--------|--------|--------|--------|--------|--
            GGGGGGGGGGGGGGGGGGG           HHHHHHHH        IIIIIIIIIIIII
--|--------|--------|--------|--------|--------|--------|--------|--------|--

The assignment of any particular box to any particular row isn't important. What I want is an algorithm which will pack these boxes into the smallest number of rows.

Is there a known algorithm for this?

slava
  • 1,901
  • 6
  • 28
  • 32
spraff
  • 32,570
  • 22
  • 121
  • 229
  • To me this seems like a variation of the [Subset-sum problem](https://en.wikipedia.org/wiki/Subset_sum_problem). – ThreeFx Sep 05 '14 at 09:51

5 Answers5

2

I've solved identical problem with the following solution:

  1. Find LB = min(startTime) and RB = max(endTime).
  2. Add empty row with length LB to RB;
  3. For each "free time" sector in the row (initially there will be only one sector: LB to RB):
    • 3.1 Find the longest element that will fit in the sector;
    • 3.2.1 If there is such element - embed in in the line;
    • 3.2.2 Otherwise it's obvious that this free sector is unusable;
  4. If there are still elements left after all current free sectors have been tested, go to 2.

Be aware, that when inserting an element (step 3.2.1), the set of free sectors being enumerated (step 3) will change.

July
  • 21
  • 3
2

The International Timetabling Competition 2007 had a lesson scheduling track and exam scheduling track. Many researchers participated in that competition. Lots of heuristics and metaheuristics were tried, but in the end the local search metaheuristics (such as Tabu Search and Simulated Annealing) clearly beat other algorithms (such as genetic algorithms).

Take a look at the 2 open source frameworks used by some of the finalists:

JBoss OptaPlanner (Java, open source) Unitime (Java, open source) - more for universities

-- Geoffrey De Smet : Algorithm for creating a school timetable

Reference:

Community
  • 1
  • 1
Margus
  • 19,694
  • 14
  • 55
  • 103
  • This unfortunately solves a different problem than the one stated in the OP. If the starting and end times are fixed as in the original question, there is no need to use combinatorial optimization. This solution is for the case where the start and end times are not fixed, but rather only the length of individual time slots and they have to be packed as efficiently as possible. – Antti Huima Sep 08 '14 at 11:47
0

I would just pack them greedily (proceed from left to right and add an event to the first track in top-down direction where it fits). It's fast and it's deterministic and most likely produces in practice good results.

Antti Huima
  • 25,136
  • 3
  • 52
  • 71
  • I tried that a few years ago and found it was often quite wasteful. – spraff Sep 05 '14 at 11:10
  • You can improve the greedy aproach a little bit by sorting the intervalls. Start with the longest interval. Just a heuristic, but should help to reduce gaps. – Matthias Sep 05 '14 at 11:11
0

This is known as Interval Partitioning. The greedy algorithm that assigns boxes in order of starting time and puts a box into the first row where it fits (or opens a new row if it fits nowhere) gives an optimal result. See for example Kleinberg&Tardos: "Algorithm Design".

Falk Hüffner
  • 4,942
  • 19
  • 25
0

If I understood your problem correctly, it is most important to find out, which dates overlap. You did not say, if the algorithm should be really efficient, or if it should work for really large data. Therefore I would recommend the following steps:

  1. Find out which dates overlap with each other. Maybe in a map, where you map each entry to a list of entries that overlap with it.
  2. Sort the element by there starting time.
  3. As long, as there is space in one row pick the element with the element with the closest starting time to the end time of the last element.
  4. From all elements that overlap with this one, choose the one with the most overlaps, that does not overlap with the previous one and add it to your row.
  5. If a row is full, check for the biggest gap and look if a element fits into it; else move on to the next row.

Maybe the weighting of the elements by overlaps and this final check in step 5. could help to improve a normal greedy approach.

Alex VII
  • 930
  • 6
  • 25