c - How to find all pairs in a list of pairs has overlaps?

Question

An array containing a list of 2 number pairs: [n1 n2...]

Each element is <first second >.

How do I efficiently find all possible overlaps?

I can think only of the brute force approach with complexity O(n2).

This problem might apply to time overlapping also.

Answer 1

Sort time by start time. Then check if next time slot start time is higher than current slot end time.

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();
}

It works in time O(n log n) where n is number of time slots

If you need to find all conflicted pairs then you need to modify algorithm:

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;
    }
}

It works in time O((n log n) + c) where n is number of time slots and c is number of conflicts

If you need only number of overlaps there is better algorithm using binary search:

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;

It works in time O(n log n).

Answer 2

The algorithm for doing this is simple enough.

1. Sort your intervals according to start time
2. Go through the list, and check if the current elements end time is greater than the next elements start time.
3. Profit

Edit

To detect all overlaps (ie. overlaps spanning multiple intervals) do:

1. Sort you intervals according to start time
2. Check the current elements end time and see if its greater than or equal to the next elements start time.
3. if this is the case mark interval as overlaping, and check the next + 1 elements start time for overlap. Continue this until you reach the end.

Do this for all intervals in the list.

Note that both "algorithms" run in O(n log n). The first one because sorting takes O(n log n) and running through the list takes O(n) giving O(n log n + n) = O(n log n). For the second one sorting is still O(n log n) and running through the list is now O((1/2)n^2 + (1/2)n) = O(n^2) giving O(n log n + n^2) = O(n^2).

Edit again
An even better way of doing this, is apparently holding you intervals in an interval tree.

Answer 3

Just sort them by start_time, then iterate over the list checking that current.end_time is not after next.start_time.