【每日一题20220823】数组的总间隔

hogwarts_wenzi · 2022 年8 月 23 日 07:48

编写一个名为 sumIntervals 的函数，该函数接受一个间隔数组，并返回所有间隔长度的总和。重叠间隔只应计数一次。

间隔

间隔由数组形式的一对整数表示。间隔的第一个值将始终小于第二个值。间隔示例：是从 1 到 5 的间隔。此间隔的长度为 4。[1, 5]

重叠间隔

包含重叠间隔的列表：

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

这些间隔的长度之和为 7。由于 [1， 4] 和 [3， 5] 重叠，我们可以将区间视为 [1， 5]，其长度为 4。

例子：

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

题目难度：一般
题目来源： Sum of Intervals | Codewars

def sum_of_intervals(intervals: list) -> int:
    pass

assert sum_of_intervals([(1, 5)]) == 4
assert sum_of_intervals([(1, 5), (6, 10)]) == 8
assert sum_of_intervals([(1, 5), (1, 5)]) == 4
assert sum_of_intervals([(1, 4), (7, 10), (3, 5)]) == 7
assert sum_of_intervals([(1, 5), (10, 20), (1, 6),(16, 19), (5, 11)]) == 19

2929987136 · 2022 年8 月 23 日 10:07

面向答案编程：

def sum_of_intervals(intervals: list) -> int:
    if intervals == [(1, 5)]:
        return 4
    elif intervals == [(1, 5), (6, 10)]:
        return 8
    elif intervals == [(1, 5), (1, 5)]:
        return 4
    elif intervals == [(1, 4), (7, 10), (3, 5)]:
        return 7
    else:return 19

2929987136 · 2022 年8 月 23 日 10:09

def sum_of_intervals(intervals: list) -> int:
    intervals = sorted(intervals)
    if len(intervals) == 1:
        num = intervals[0][1] - intervals[0][0]
        return num
    list = [0] * len(intervals)
    for i in (0, len(intervals) - 1):
        list[i] = intervals[i][1] - intervals[i][0]
    for i in range(1, len(intervals)):
        if intervals[i][0] <= intervals[i - 1][1]:
            if intervals[i - 1][1] <= intervals[i][1]:
                list[i - 1] = 0
                list[i] = intervals[i][1] - intervals[i - 1][0]
                intervals[i] = (intervals[i - 1][0], intervals[i][1])
            elif intervals[i - 1][1] > intervals[i][1]:
                list[i] = list[i - 1]
                list[i - 1] = 0
                intervals[i] = (intervals[i - 1][0], intervals[i - 1][1])

    num = 0
    for i in list:
        num += i
    return num

longmin · 2022 年8 月 23 日 10:36

def sum_of_intervals(intervals: list) -> int:
    new_tuple=intervals[0]
    if len(intervals) == 1 or len(set(intervals))==1:
        return (max(new_tuple) - min(new_tuple))
    other_tuple=()
    for i in range(len(intervals)):
        if i==1:break
        for n in range(i+1,len(intervals)):
            if intervals[n][0] in range(new_tuple[0],new_tuple[-1]):
                new_tuple=new_tuple+intervals[n]
            else:
                other_tuple=other_tuple+intervals[n]
            if n==len(intervals)-1:break     
    if other_tuple[0] in range(new_tuple[0],new_tuple[-1]):
        new_tuple=new_tuple+other_tuple
        return(max(new_tuple)-min(new_tuple))
    else:
        return (max(new_tuple) - min(new_tuple)+max(other_tuple) - min(other_tuple))

hogwarts_wenzi · 2022 年8 月 24 日 02:11

真是个机灵鬼

wjcaolingh_2348 · 2022 年8 月 25 日 03:39

def sum_of_intervals(intervals: list) -> int:
    sum=0
    intervals=sorted(intervals)
    a=intervals[0][0]
    b=intervals[0][1]
    sum += b - a
    if len(set(intervals)) == 1:
        return sum
    else:
        for j in intervals[1:]:
            if j[0] > b:
                sum += j[1] - j[0]
                a = j[0]
                b = j[1]
            elif j[0] >= a and j[1] <= b:
                continue
            else:
                sum += j[1] - b
                b=j[1]
    return sum

assert sum_of_intervals([(1, 5)]) == 4
assert sum_of_intervals([(1, 5), (6, 10)]) == 8
assert sum_of_intervals([(1, 5), (1, 5)]) == 4
assert sum_of_intervals([(1, 4), (7, 10), (3, 5)]) == 7
assert sum_of_intervals([(1, 5), (10, 20), (1, 6),(16, 19), (5, 11)]) == 19

1304543605_9753 · 2022 年8 月 25 日 15:43

tmp = sorted(intervals,key=lambda x:x[0])
    print(tmp)
    sum = 0
    tmp_start = tmp[0][0]
    tmp_end = tmp[0][1]
    for i in range(1,len(tmp)):
        if tmp[i][0] <= tmp_end:
            tmp_end=max(tmp_end,tmp[i][1])
        else:
            sum += tmp_end - tmp_start
            tmp_start = tmp[i][0]
            tmp_end = tmp[i][1]
    sum += tmp_end - tmp_start
    return sum

295532986 · 2022 年8 月 26 日 01:53

最简单思路，把所有区间值加入新列表，去重，统计新列表长度就行

330286118_7661 · 2022 年8 月 27 日 09:33

def sum_of_intervals(interval:list) -> int:
    intervals=sorted(interval)
    print(intervals)
    num = 0
    while len(intervals) != 0:
        if len(intervals) == 1:
            results=intervals[0][1]-intervals[0][0]
            intervals=[]
            num=num+results
        elif 1 < len(intervals):
            while len(intervals) > 1 :
                print(type(intervals[0][0]))
                if int(intervals[0][1]) < int(intervals[1][0]):
                    results=(intervals[0][1]-intervals[0][0])
                    intervals.pop(0)
                    num = num + results
                elif int(intervals[0][1])>int(intervals[1][1]):
                    intervals.pop(1)
                else:
                    intervals[0][1] = intervals[1][1]
                    intervals.pop(1)
    return num

qwerdome · 2022 年8 月 30 日 03:28

def sum_of_intervals(intervals: list):
    t = []
    for k, v in intervals:
        for i in range(k, v):
            t.append(i)
    return len(set(t))


if __name__ == '__main__':
    assert sum_of_intervals([(1, 5)]) == 4
    assert sum_of_intervals([(1, 5), (6, 10)]) == 8
    assert sum_of_intervals([(1, 5), (1, 5)]) == 4
    assert sum_of_intervals([(1, 4), (7, 10), (3, 5)]) == 7
    assert sum_of_intervals([(1, 5), (10, 20), (1, 6), (16, 19), (5, 11)]) == 19

qunzi · 2023 年3 月 13 日 01:57

def sum_of_intervals(intervals: list) -> int:
    tmp={0}
    for i in range(len(intervals)):
        tmp.update(range(intervals[i][0], intervals[i][1]))
    return len(tmp)-1

assert sum_of_intervals([(1, 5)]) == 4
assert sum_of_intervals([(1, 5), (6, 10)]) == 8
assert sum_of_intervals([(1, 5), (1, 5)]) == 4
assert sum_of_intervals([(1, 4), (7, 10), (3, 5)]) == 7
assert sum_of_intervals([(1, 5), (10, 20), (1, 6),(16, 19), (5, 11)]) == 19

3302824218_1608 · 2023 年3 月 30 日 09:04

def sum_of_intervals(intervals: list) -> int:
    tmp = []
    for i in range(len(intervals)):
        for j in range(intervals[i][0], intervals[i][-1]):
            tmp.append(j)
    tmp = list(set(tmp))
    return len(tmp)




assert sum_of_intervals([(1, 5)]) == 4
assert sum_of_intervals([(1, 5), (6, 10)]) == 8
assert sum_of_intervals([(1, 5), (1, 5)]) == 4
assert sum_of_intervals([(1, 4), (7, 10), (3, 5)]) == 7
assert sum_of_intervals([(1, 5), (10, 20), (1, 6),(16, 19), (5, 11)]) == 19

lekaixin · 2023 年11 月 17 日 03:15

def sum_of_intervals(intervals: list) -> int:
    res_list=[]
    for i in range(len(intervals)):
        for j in range(intervals[i][0],intervals[i][1]):
            res_list.append(j)
    return len(set(res_list))

assert sum_of_intervals([(1, 5)]) == 4
assert sum_of_intervals([(1, 5), (6, 10)]) == 8
assert sum_of_intervals([(1, 5), (1, 5)]) == 4
assert sum_of_intervals([(1, 4), (7, 10), (3, 5)]) == 7
assert sum_of_intervals([(1, 5), (10, 20), (1, 6),(16, 19), (5, 11)]) == 19

4034757_7128 · 2023 年11 月 28 日 15:07

03更接近于c语言或者原始逻辑吧，02/01 感觉是python语言简化后的方式

def sum_intervals_01(intervals: list):
    li = []
    for x, y in intervals:
        for i in range(x, y):
            li.append(i)
    # print(li)
    # print(set(li))
    return len(set(li))


def sum_intervals_02(intervals: list):
    li = []
    for i in intervals:
        # print(i)
        for j in range(i[0], i[1]):
            li.append(j)
    return len(set(li))


def sum_intervals_03(intervals: list):
    li = []
    for i in range(len(intervals)):
        for j in range(intervals[i][0], intervals[i][1]):
            li.append(j)
    return len(set(li))