Build duration calculation

stuff about computer science and programming
Post Reply
User avatar
dendiz
Site Admin
Posts: 114
Joined: Wed Oct 10, 2018 3:48 am

Build duration calculation

Post by dendiz » Wed Oct 10, 2018 10:50 pm

While browsing the GitLab pipeline documentation I came across this:
14.png
14.png (51.62 KiB) Viewed 68 times
his 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

Code: Select all

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

Code: Select all

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

Code: Select all

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

Code: Select all

S = (1,4) (6,7)
no more elements left to pop the stack

element (6,7) → difference 1, sum 1

Code: Select all

S = (1,4)
element (1,4) → different 3, sum 4

Code: Select all

S = []
total duration is 4.

Code: Select all

  public static class Interval {
       public int start;
       public int end;

       public Interval(int start, int end) {
           this.start = start;
           this.end = end;
       }
   }

   public int totalDuration(List<Interval> intervals) {
       if (intervals.isEmpty()) return 0;
       Stack<Interval> stack = new Stack<>();
       stack.push(intervals.get(0));
       for(int i=1;i<intervals.size();i++) {
           if (intervals.get(i).start < stack.peek().end) {
               stack.peek().end = intervals.get(i).end;
           } else {
               stack.push(intervals.get(i));
           }
       }
       int total = 0;
       while(!stack.empty()) {
           Interval interval = stack.pop();
           total += interval.end - interval.start;
       }
       return total;
   }

Post Reply