Problem: Given a set of n intervals I = [a1, b1],[a2, b2], . . .[an, bn]. Here ai < bi for all i = 1 to n. Devise a Divide and Conquer algorithm to compute the length of the biggest overlap between any two intervals in O(nlogn) time. Justify the time complexity. For eg, [1, 7] overlaps with [3, 9], and the length of the overlap between them is 7 − 3 = 4.
My approach:
Sort the intervals on the basis of ais.
Initialize a variable max_interval = INT_MIN.
Traverse through the intervals . For every interval, check if the next one is a subinterval. If yes then merge the intervals and update max_interval by the length of the subinterval when it is greater than its current value. This can be done in O(n) + O(nlogn) = O(nlogn)
Apply divide and conquer method. We divide the set on the basis of the median of ais.
Return max of the answer returned by the left set, right set and the overlap between rightmost interval of the left set with the leftmost interval of the right set.
The recurrence relation for this will be T(n) = 2T(n/2) + O(1) => T(n) = O(logn)
So the overall time complexity is O(nlogn).
How can I prove the correctness of this algorithm?