合并区间 Merge intervals

56. 合并区间

55. 跳跃游戏

2580. 统计将重叠区间合并成组的方案数

2584. 分割数组使乘积互质

100136. 统计好分割方案的数目

合并区间的两种写法
考虑如下数组
[3,1,2,1,2,4,4]
题目要求相同数字必须在同一个子数组中，所以两个 1 必须在同一个子数组，两个 2 也必须在同一个子数组。所以 [1,2,1,2][1,2,1,2] 这一段必须是完整的，不能分割。

把该数组分到无法再分，得到 [3] + [1,2,1,2] + [4,4]
考虑每个 + 号选或不选，一共有 2²=4 种好分割方案，即
[3]+[1,2,1,2]+[4,4]
[3]+[1,2,1,2,4,4]
[3,1,2,1,2]+[4,4]
[3,1,2,1,2,4,4]
​
写法一：合并区间
用一个哈希表/有序集合记录每个元素首次出现的位置和最后一次出现的位置，每个元素就对应着一个不可分割的区间。然后按照 56. 合并区间 的做法，把这些区间都合并起来。假设合并后的区间个数为 m，那么答案就是 2^m-1 记得取模。

注意代码中少统计