c - 如何找到对列表中所有有重叠的对？

Question

包含 2 个数字对的列表的数组:[n1 n2...]

每个元素是<first second > .

如何有效地找到所有可能的重叠？

我只能想到复杂度为 O(n2) 的蛮力方法。

此问题也可能适用于时间重叠。

Answer 1

按开始时间对时间进行排序。 然后检查下一个时间段开始时间是否高于当前时间段结束时间。

TimeSlot[] slots;
sort(slots, slots.start_time);
for(i = 0 to (slots.length - 1)){
    if(slots[i].end_time > slots[i + 1].start_time) reportConflict();
}

它的工作时间O(n log n)，其中n是时隙数

如果您需要查找所有冲突对，那么您需要修改算法:

TimeSlot[] slots;
sort(slots, slots.start_time);
for(i = 0 to (slots.length - 1)){
    int j = i + 1;
    while(j < (slots.length - 1) and slots[i].end_time > slots[j].start_time){
        reportConflict(i, j);
        ++j;
    }
}

它的工作时间为O((n log n) + c)，其中n是时隙数，c是时隙数冲突

如果您只需要重叠数，则可以使用二分搜索更好的算法:

TimeSlot[] slots;
int overlapsNumber = 0;
sort(slots, slots.start_time);
for(i = 0 to (slots.length - 1)){
    int j = BinarySearch(slots, i);
    overlapsNumber += (j - i);
}

//Finds index j which is the greatest index that slots[j].start_time < slots[i].end_time
int BinarySearch(TimeSlot[] sortedSlots, int pos){
    int b = pos, e = sortedSlots.length - 1;
    int ans = b;
    while(b < e){
        int mid = (e + b) / 2;
        if(sortedSlots[mid].start_time < sortedSlots[pos].end_time){
            ans = mid;
            b = mid + 1;
        } else {
            e = mid - 1;
        }
    }
    return ans;

它的工作时间O(n log n)。