CODEWITHSUNDEEP
arraysalgorithmsorting
user1480192
user1480192

Reputation: 863

Algorithm to check overlap between arrays

I have two arrays, one of existing appointments and one of potential appointments. The arrays each contain from/to values of the existing or potential appointments. The appointments in each array are already sorted by the from time.

I need to check each of the potential appointments against each of the existing appointments to see that there is no overlap. I know I can start from the beginning of the existing appointments each time but I am looking for a more efficient way.

Upvotes: 3

Views: 3711

Answers (4)

amit
amit

Reputation: 1

if we first join these two arrays and the time required for joining is O(n) and then we sort the whole array and this sorting required O(nlogn) if we use quick sort or merge sort then if we compute the total time complexity, it will be like this

F(n) = O(n) + O(nlogn)

so final complexity will be O(nlogn) which is laser than O(n^2)

Upvotes: 0

Rishit Sanmukhani
Rishit Sanmukhani

Reputation: 2269

This can be done efficiently in O(nlogn). Consider two arrays A, B containing existing and potential appointments respectively. Sort A in increasing order of ending times of appointments (A_end) and starting time of appointments (A_start). This takes O(nlogn) time

For each potential appointment in B:
s = starting point of the assignment
t = ending point of the assignment

Now, binary search on array A_start and A_end to find all the appointments that fall between s-t taking o(logn) time.
[# Overlaps =
(appointments with ending time <= t) - (appointments with ending time < s) +
(appointments with ending time > t) - (appointments with starting time > t) +
]

Thus, overall order is O(nlogn)

EDIT: #overlaps = sum_1 + sum_2
Here sum_1 represents those intervals with ending time <= t. But again to only find the overlapping intervals we have to subtract those intervals with ending time < s. Thus, we get only those with ending time >=s and <=t.
Here sum_2 represents those intervals with ending time > t. But again to only find the overlapping intervals we have to subtract those intervals with ending time > t. Thus we get only those with ending time >t but starting time <=t.

Proof can be given by the fact that any overlapping interval can either have ending time <=t or >t. Thus it will either lie in sum_1 or sum_2.

Upvotes: 1

BKE
BKE

Reputation: 573

You can take the union of the the existing and potential appointments into a single array, and sort the union by start time. Add a label to the intervals so you know it was an existing or a potential interval. (You can also sort them in separate arrays and increment two indices, but the code is simpler with one list).

You can then loop through the combined array, and merge together neighboring intervals if they overlap. Only merge existing appointments with existing, and likewise, potential appointments with potential. For this, you have to memorize the most recent existing and potential intervals.

This way, you do not need to go back to the very beginning, you only need to look at the most recently merged intervals.

In psedudocode:

E: existing appointments
P: potential appointments

A: union of P and E, sorted by start time

lastE = []
lastP = []
for each appointment a in A:
    if a is existing:
        if a overlaps with lastE:
            lastE = lastE + [a]
        else
            lastE = [a]
        if a overlaps with lastP:
            print all appointments in lastP overlapping with a
    if a is potential:
        if a overlaps with lastE:
            print a
        if a overlaps with lastP:
            lastP = lastP + [a]
        else:
            lastP = [a]

Note, that you need not store the structure of lastE, you can define it as a single interval and adjust the start and end time.

You need to know the individual appointments in lastP though. You can possibly optimize it even further by maintaining a descending order by end time in lastP. Then, on the line when all overlaps between a and lastP are printed, you can stop looking once the end time of the potential appointment in lastP is smaller than the start time of a.

Upvotes: 0

Patrick87
Patrick87

Reputation: 28292

The idea: start comparing the first intervals to each other. If one interval comes entirely before the other, look at the next interval until you find one that overlaps or comes after. Either interval A comes entirely before interval B, or B comes entirely before A, or they overlap somehow. Once you find an overlap, you can quit looking. This can be made to easily return the earliest overlapping pair, but returning all overlapping pairs would require more work.

Pseudocode:

Overlaps(actual[1..n], pending[1..m])
    i = 1
    j = 1
    while i <= n and j <= m do
        if actual[i].stop <= pending[j].start then
            i = i + 1
        else if actual[i].start >= pending[j].stop then
            j = j + 1
        else
            return true
    return false

Note - if you want to find all overlapping pairs, instead of quitting after detecting the first overlap, you could just print out i and j and increment i if actual[i].stop <= pending[j].stop or increment j if actual[i].stop > pending[j].stop. That would end up printing every overlapping pair and is still linear time.

Upvotes: 1

Related Questions