如何做数字的区间并集，就像你在数学中做的那样

Question

如何像数学一样进行区间并集。例如，范围1到3和2到4在连接时会产生范围1到4，因为它们的部分重合。

因此输入：[1,3][2,4]

将具有输出：[1,4]。

但输入：[1,3][4,5]

输出：

[1,3][4,5]

将产生[1，3][4，5]，因为区间的任何部分都不匹配。函数必须能够连接字符串中给定的各种范围(可能不符合顺序(

例如：

输入：

[1,3][3,4][5,8][6,10]

输出：

[1,4][510]

Answer 1

也许你可以根据区间的起始值对区间进行排序，然后检查每个区间是否应该合并：

from typing import NamedTuple
from prettytable import PrettyTable
def merged_intervals(intervals: list[list[int]]) -> list[list[int]]:
if not intervals:
return []
sorted_intervals = sorted(intervals, key=lambda i: i[0])
merged = [sorted_intervals[0]]
for start, end in sorted_intervals[1:]:
if merged[-1][1] >= start:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
class TestCase(NamedTuple):
intervals: list[list[int]]
expected: list[list[int]]
def main() -> None:
t = PrettyTable(['intervals', 'expected', 'actual'])
t.align = 'l'
for intervals, expected in [TestCase([[1, 3], [2, 4]], [[1, 4]]),
TestCase([[1, 3], [4, 5]], [[1, 3], [4, 5]]),
TestCase([[1, 3], [3, 4], [5, 8], [6, 10]],
[[1, 4], [5, 10]])]:
t.add_row([intervals, expected, merged_intervals(intervals)])
print(t)
if __name__ == '__main__':
main()

输出：

+-----------------------------------+-------------------+-------------------+
| intervals                         | expected          | actual            |
+-----------------------------------+-------------------+-------------------+
| [[1, 4], [2, 4]]                  | [[1, 4]]          | [[1, 4]]          |
| [[1, 3], [4, 5]]                  | [[1, 3], [4, 5]]  | [[1, 3], [4, 5]]  |
| [[1, 4], [3, 4], [5, 8], [6, 10]] | [[1, 4], [5, 10]] | [[1, 4], [5, 10]] |
+-----------------------------------+-------------------+-------------------+