Sum of Intervals

Sum of Intervals

Write a function called sumIntervals/sum_intervals() that accepts an array of intervals, and returns the sum of all the interval lengths. Overlapping intervals should only be counted once.

Intervals

Intervals are represented by a pair of integers in the form of an array. The first value of the interval will always be less than the second value. Interval example: [1, 5] is an interval from 1 to 5. The length of this interval is 4.

Overlapping Intervals

List containing overlapping intervals:

[
   [1,4],
   [7, 10],
   [3, 5]
]

The sum of the lengths of these intervals is 7. Since [1, 4] and [3, 5] overlap, we can treat the interval as [1, 5], which has a length of 4.

Examples:

sumIntervals( [
   [1,2],
   [6, 10],
   [11, 15]
] ); // => 9

sumIntervals( [
   [1,4],
   [7, 10],
   [3, 5]
] ); // => 7

sumIntervals( [
   [1,5],
   [10, 20],
   [1, 6],
   [16, 19],
   [5, 11]
] ); // => 19

// null argument
Interval.sumIntervals(null);  // => 0

// empty intervals
Interval.sumIntervals(new int[][]{});  // => 0
Interval.sumIntervals(new int[][]{2,2}, {5,5});  // => 0

// disjoined intervals
Interval.sumIntervals(new int[][]{
  {1,2},{3,5}
});  // => (2-1) + (5-3) = 3

// overlapping intervals
Interval.sumIntervals(new int[][]{
  {1,4},{3,6},{2,8}
});  // [1,8] => 7

// empty intervals
Intervals.SumIntervals(new (int, int)[]{ });  // => 0
Intervals.SumIntervals(new (int, int)[]{ (2, 2), (5, 5)});  // => 0

// disjoined intervals
Intervals.SumIntervals(new (int, int)[]{
  (1, 2), (3, 5)
});  // => (2-1) + (5-3) = 3

// overlapping intervals
Intervals.SumIntervals(new (int, int)[]{
  (1, 4), (3, 6), (2, 8)
});  // (1,8) => 7

sum_intervals( {
   {1,2},
   {6, 10},
   {11, 15}
} ); // => 9

sum_intervals( {
   {1,4},
   {7, 10},
   {3, 5}
} ); // => 7

sum_intervals( {
   {1,5},
   {10, 20},
   {1, 6},
   {16, 19},
   {5, 11}
} ); // => 19

sum_intervals((const struct interval[]){
   {1,2},
   {6, 10},
   {11, 15}
}, 3); /* => 9 */

sum_intervals((const struct interval[]){
   {1,4},
   {7, 10},
   {3, 5}
}, 3); /* => 7 */

sum_intervals((const struct interval[]){
   {1,5},
   {10, 20},
   {1, 6},
   {16, 19},
   {5, 11}
}, 5); /* => 19 */

v1:
    dd    1,2, \
          6,10, \
          11,15
v2:
    dd    1,4
    dd    7,10
    dd    3,5
v3:
    dd    1,5, 10,20, 1,6, 16,19, 5,11

    mov rdi, v1
    mov rsi, 3
    call sumintvls    ; EAX <- 9

    mov rdi, v2
    mov rsi, 3
    call sumintvls    ; EAX <- 7

    mov rdi, v3
    mov rsi, 5
    call sumintvls    ; EAX <- 19

(sum-intervals [ [1 5] [10 15] [-1 3] ]) ; => 11

(sum-intervals [ [1 5] ]) ; => 4

sumOfIntervals([[1, 5], [10, 15], [-1, 3]]) // => 11

sumOfIntervals([[1, 5]]) // => 4

sum_of_intervals([{1, 5}, {10, 15}, {-1, 3}]) # => 11

sum_of_intervals([{1, 5}]) # => 4

sum_of_intervals([{1, 5}, {10, 15}, {-1, 3}]) # => 11

sum_of_intervals([{1, 5}]) # => 4

sumOfIntervals([(1, 5}, (10, 15}, (-1, 3)]) -- => 11

sumOfIntervals([(1, 5)]) -- => 4

sumofintervals([(1, 5}, (10, 15}, (-1, 3)]) # => 11

sumofintervals([(1, 5)]) # => 4

sumOfIntervals([[1, 5], [10, 15], [-1, 3]]) // => 11

sumOfIntervals([[1, 5]]) // => 4

(sum-intervals (list (list -1 21) (list -59 -45))) ;; 36
(sum-intervals (list (list 1 5) (list 10 15) (list -1 3))) ;; 11
(sum-intervals (list (list 1 2) (list 6 10) (list 11 15))) ;; 36

Solutions

🐍 Python

def sum_of_intervals(intervals):
    for _ in range(3):
        valid_intervals = [list(intervals[0])]

        for n, itrl in enumerate(intervals[1:]):
            is_sub_interval = False
            for k, v_itrl in enumerate(valid_intervals):
                # [  (     ]  )
                if v_itrl[0] <= itrl[0] and v_itrl[1] >= itrl[0]:
                    is_sub_interval = True
                    if  itrl[1] > v_itrl[1]:
                        valid_intervals[k][1] = itrl[1]
                # (  [     )  ]
                elif v_itrl[1] >= itrl[1] and v_itrl[0] <= itrl[1]:
                    is_sub_interval = True
                    if  itrl[0] < v_itrl[0]:
                        valid_intervals[k][0] = itrl[0]

            if not is_sub_interval:
                valid_intervals.append(list(itrl))

            intervals=list(reversed(valid_intervals))    

    return sum(x[1]-x[0] for x in valid_intervals)