https://www.codewars.com/kata/sum-of-intervals/train/python

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复制

普通的思路：

先用双指针合并区间，然后再遍历合并好的区间统计总长度。

时间复杂度：O（NlogN）

空间复杂度：O（1）

def sum_of_intervals(intervals):
    if not intervals:
        return 0
    def merge_intervals(intervals):
        intervals.sort()
        res = []
        start, end = intervals[0][0], intervals[0][1]
        
        for i, interval in enumerate(intervals[1:]):
            s, e = interval[0], interval[1]
            if s > end:
                res.append([start, end])
                start, end = s, e
            else:
                end = max(e, end)
        res.append([start, end])
        return res
            
        
    intervals = merge_intervals(intervals)
    res = 0
    for s, e in intervals:
        res += e - s
        
    return res复制

奇淫巧技的思路：

把所有区间里的数丢到一个集合里，然后统计集合的长度即可。

时间复杂度：O（N），N是intervals长度

空间复杂度：O（N*M），M是最长的那个interval的长度

def sum_of_intervals(intervals):
    l = []
    for s, e in intervals:
        l += range(s, e)
    return len(set(l))复制

或者Codewars经典的一行解。

def sum_of_intervals(intervals):
    return len(set(i for s, e in intervals for i in range(s, e)))复制