sum of intervals kata in codewars

Question

instructions for the kata:
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

sumIntervals( [
   [0, 20],
   [-100000000, 10],
   [30, 40]
] ) => 100000030

Tests with large intervals
Your algorithm should be able to handle large intervals. All tested intervals are subsets of the range [-1000000000, 1000000000].

I tried

def sum_of_intervals(intervals):
    total=set()
    for interval in intervals:
        for x in range(interval[0],interval[1]):
            total.add(x)
    return len(total)

but it doesn't work due to timed out error,could you help me with optimizing the code or can you come up with a better algorithm?

Answer 1

Naming

instructions for the kata:
Write a function called sumIntervals/sum_intervals() that ...

You named your function sum_of_intervals(), which is not what the question asked for.

PEP-8

The Style Guide for Python Code recommends leaving a space around binary operators. total=set() should be written total = set().

Additionally, it recommends a space after any comma that is followed by more content, so range(interval[0],interval[1]) should be range(interval[0], interval[1])

Readability

interval[0] and interval[1] read like they are two different intervals: interval #0 and interval #1. You should give descriptive names to these values. Python allows you to use a "tuple assignment"-like syntax in the for statement itself, making this virtually free:

    for interval_start, interval_end in intervals:
        for x in range(interval_start, interval_end):

Use Standard Library Functions

You can add multiple items to a set at once. In particular, this loop

        for x in range(interval_start, interval_end):
            total.add(x)

could be eliminated and replaced with one statement:

        total.update(range(interval_start, interval_end))

(This should be faster than doing the loop yourself, but always profile to make sure.)

Updated Code

def sum_intervals(intervals):

    total = set()

    for interval_start, interval_end in intervals:
        total.update(range(interval_start, interval_end))

    return len(total)

Algorithmic improvement

Your code's real problem is in time and space complexity. Given the interval [-1000000000, 1000000000] your code will add two billion numbers to the total set. This takes \$O(N)\$ time and \$O(N)\$ space. In contrast, we can calculate the length of the interval in \$O(1)\$ time, in \$O(1)\$ space, using subtraction.

You've used a set() to handle overlaps. Clearly, that leads to timeout error. You need a different approach.

Consider:

>>> intervals = [[1, 5], [10, 20], [1, 6], [16, 19], [5, 11]]

Would re-ordering the intervals help you identify and remove overlaps?

>>> sorted(intervals)
[[1, 5], [1, 6], [5, 11], [10, 20], [16, 19]]

Exercise left to student.