0
\$\begingroup\$

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?

\$\endgroup\$
1
  • \$\begingroup\$ It would be helpful if you clearly identified which CodeWars challenge it was and perhaps a link to the CodeWars question. \$\endgroup\$
    – pacmaninbw
    Dec 28, 2022 at 13:52

1 Answer 1

1
\$\begingroup\$

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.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.