假设我有一个时间范围数组，如下所示：
[
{ name: 'A', startTime: '10:15', endTime: '11:15'},
{ name: 'B', startTime: '10:45', endTime: '14:15'},
{ name: 'C', startTime: '15:35', endTime: '16:15'},
{ name: 'D', startTime: '11:30', endTime: '16:20'},
{ name: 'E', startTime: '10:30', endTime: '18:00'},
]
看起来是这样的（视觉上）：
|---A---|_____________________________________________________________________|------B------|_____________________________________________________________________________|----C----|_________________________________________________|-----------D-----------|________________________________________|-------------------E---------------------|___________________________我不想以导致
array of arrays的方式安排间隔，以便：数组的每个间隔，
does not intersect with ANY other interval in that array。（最终结果的可视化表示）：
[
[ A, D ],
[ B, C ],
[ E ]
]
数组的总数绝对是可能的最小数目。
（我的意思是，如果一个元素与第一个数组相交，而不是与创建的第二个数组相交，不要创建第三个数组，将它放在第二个数组中）
性能是必需的（最简单的方法是遍历每个元素以确定它是否相交，但这将像疯狂一样消耗资源），因此比o（n^2）更好的性能会更好。
有什么想法吗？
谢谢您。
最佳答案
你可以这样做：
将第一个间隔设置为a0
第二次休息。如果它不与一个集合中的间隔相交，那么将它放在这样的集合中，如果它考虑下一个集合。如果它与所有集合相交，则创建一个新集合并将其放在那里。
用一个简单的实现来检查带有set的intersection，这是o（n^2）。但是，对于每个集合，我们可以保持一个二叉树排序间隔。因为集合中的间隔不相交，所以它们之间有一个完整的顺序这样，为了检查间隔i是否与树中的间隔相交，我们可以如下遍历树：
如果我与当前节点n相交，则返回true
如果I.right < N.left，则移到左边的子项
如果I.left > N.right，请移到正确的子级
因为我们可以以log（m）步遍历树（其中m是集合的大小，我们得到o（n x（n/m）x logm）。如果没有间隔重叠，则为O（N x logN）如果所有间隔重叠，则为O（N x N）为了进一步改进这种最坏的情况，可以将树组织为二叉树、间隔树或扩充树（请参见https://en.wikipedia.org/wiki/Interval_tree），这样就不需要遍历所有的集合。
关于arrays - 算法:如何根据时间事件是否重叠来重新安排时间范围事件(间隔)列表，比O(n ^ 2)还快？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/41028061/