Build Pipeline duration calculation

May 9, 2019 programming

While browsing the GitLab pipeline documentation I came across this:

this got me thinking about how this calculation could be done. I’m assuming here that there is an unlimited number of CPUs so tasks can run in parallel.

  1. sort the input pair by arrival time
  2. push the first pair on a stack
  3. for each of the remaining pairs do these
    1. if current pair start < stack top end push it on the stack
    2. else update the stack top ending time to cur end time

at the end of this the stack will contain the mutually exclusive intervals. Now iterate over this stack and subtract end time from the start time and sum up the results.

So for the input

 A (1, 3)
 B (2, 4)
 C (6, 7)

which is [(1,3), (2,4), (6,7)] and sorted, push the first one on the stack

S = (1,3)

next item is (2,4) and its start is < stack top end so update the stack top

S = (1,4)

next item is (6,7) and its start is > stack top so push it

S = (1,4) (6,7)

no more elements left to pop the stack

element (6,7)->difference 1, sum 1

S = (1,4)

element (1,4)->different 3, sum 4

S = []

total duration is 4.

Here is the java code:

buildpipeline.java