Layout algorithm for resource timings

Question

I'm trying to come up with a performant layout algorithm for web resources timings. For now, all that is relevant is that resource timings include a startTime timestamp and a duration and the goal of this layout algorithm is to assign each resource timing to a lane. A resource timing cannot be assigned to a lane if it overlaps another resource timing.

The goal of this layout algorithm is to:

1. minimize the number of lanes created (primary objective)
2. minimize the gaps between resource timings (secondary objective to break ties)

Informally, I'm looking to create an aesthetically pleasing rendering of all the resource timings but I want it to be determinate and use the output for other stats like the number of tracks and the highest count of timings within a track.

I've tried a few brute force ideas but I'm having trouble creating something performant. I'm thinking there's probably a clever way to frame this as a DP problem but I'm not seeing it 😅

Edit: I'm also trying to render these timings and lanes on a screen so I don't just need the number of lanes, I need where the timings should go as well.

---

Edit: Illustrations 😄

Here is drawing of a set of resource timings. Each box represents a resource timing. The position from the left represents the start time and length of each box represents the duration.

fig 1

I'm trying to write a layout algorithm that assigns each resource timing to a "lane". That...

...minimizes the number of lanes needed

fig 2

...and minimizes the gaps between resource timings

fig 3

Note that the last example is a better layout because it removes a gap.

• Nathaniel: How can you "minimize the gaps between resource timings" if each resource timings has a fixed startTime? (As I understand, you the time interval necessary for a resource is fixed)
• D.W.: It sounds like you are asking to simultaneously minimize multiple objectives. This is not a well-formed problem, because you haven't specified how you want to trade off between those multiple goals (which typically will be in conflict with each other). Normally we pick a single objective function to minimize. Perhaps the primary goal is to minimize the number of lanes?
• Rico Kahler: Sorry yes, minimizing lanes was meant to be the primary objective that trumps the secondary. The second objective breaks ties.
• Rico Kahler: @Nathaniel since there are choices of which lane to put a resource, it's possible to create an suboptimal layout that might share the same minimal number of lanes but there might exist another layout that placed a resource timing in a different lane that resulted in less gaps within each lane. Does that make sense? I'll try to update my question with illustrations.

Answer 1

While this problem can be represented as interval graphs, it is not necessary to solve it. Moreover, an efficient algorithm to solve the problem directly on interval graphs is LexBFS, but it is quite hard to implement. Of course, it is simpler if you already know the corresponding intervals set, but in this case, working directly on intervals without graph is simpler in my opinion.

A greedy algorithm to solve it can be described as follow:

• creating a list of events, corresponding to the beginning or the end of a task. An event is a triple (time, task, type);
• computing the number of necessary lanes;
• assigning lanes to tasks.

Input: list [(s1, d1), (s2, d2), ..., (sn, dn)] 
 containing couples (starting time, duration).
Output: mapping f : {1, ..., n} to {1, ..., m}, m being 
 the necessary number of lanes
//Creating a list of events
events ← empty list
for i = 1 to n do
 add (si, i, true) to events
 add (si + di, i, false) to events
sort events by increasing order of first component
//Computing the necessary number of lanes
lane ← 0
m ← 0
for (time, i, type) in events do
 if type then
 lane ← lane + 1
 m ← max(m, lane)
 else
 lane ← lane - 1
//Assigning lanes to tasks
available ← min-heap containing all values {1, ..., m}
for (time, i, type) in events do
 if type then
 lane ← extract_min(available)
 f(i) ← lane
 else
 insert(available, f(i))
return f

Since we use a priority queue to find the minimal available lane, and $m\leqslant n$, the algorithm is overall $\mathcal{O}(n\log n)$. I think it also satisfies the second constraint, since you always try to assign the smallest lane when possible.

Answer 2

The problem of minimizing the number of lanes is the problem of graph coloring (with the fewest number of colors) of an interval graph, namely, the graph with one vertex per resource timing and an edge between each pair of resource timings whose times overlap. Wikipedia says you can find such a graph coloring in linear time using "a greedy coloring algorithm that colors the intervals in sorted order by their left endpoints". Then, you should be able to use binary search on the number of colors, to find the minimal number of lanes needed.

• Rico Kahler: Thank you for sharing this. I wasn't aware of interval graphs and that is the perfect way to model the problem and this info is greatly helping me. However, I don't just need the number of lanes, I need to know which lane each resource timing should be assigned to because I'm rendering the result.
• D.W.: @RicoKahler, the graph coloring algorithm assigns each resource a color, i.e., a lane, so it does exactly what you want, assuming the goal is to minimize the number of lanes.