algorithm - 算法：如何将具有共同范围的集合分成每个不同的范围

Question

我已经尝试了这个问题很长一段时间，但找不到一个好的解决方案：

假设我们有整数范围，例如

 100 - 1000
 200 - 300
 500 - 600
 550 - 575
 800 - 1200
 1100 - 2300

所以我想将这些混合范围纳入每个单独的不同范围

 100 - 199
 200 - 300
 301 - 499
 500 - 549
 550 - 575
 575 - 600
 800 - 1099
 1100 - 1200
 1201 - 2300

有一些标准算法吗？

谢谢

Answer 1

将每个数字推入一个数组，排序和重复数据删除。在 C++ 中，将它们全部插入 astd::set<int>具有预期的效果。在 Python 中，您可以编写sorted(set(x for (a, b) in ranges for x in (a, b))).

在结果集合中，相邻对表示不重叠的范围。

需要注意的是，这种技术依赖于 [a, b) 约定（即，包含在左侧；排除在右侧）来描述范围。