0
$\begingroup$

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:

  1. Sort the intervals on the basis of ais.

  2. Initialize a variable max_interval = INT_MIN.

  3. 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)

  4. Apply divide and conquer method. We divide the set on the basis of the median of ais.

  5. 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?

Improve this question
$\endgroup$
1
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W. ♦
    Feb 4 at 8:13

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.