C# · 12月 27, 2021

c# – 最快的算法确定范围重叠

我有两组范围,每个范围是一对指示开始和结束的整数.确定两个范围之间是否存在重叠的最快方法是什么?

谢谢.

解决方法@H_404_7@ 如果它们都是按开始排序你可以只检查两组中的第一个范围,看看它们是否重叠,如果没有移动到具有最小结束偏移的集合中的下一个项目,则冲洗并重复直到找到重叠或者你是在一组结束时.如果已经排序,则为O(n),否则为O(n log n).