Given an array with $n>2$ elements of integer sets intervals, where each set is represented as a tuple of the form $(inf, sup)$ (with $inf $ ínfimum and $sup $ maximum of the set), we want to obtain the two intervals such that the number of elements of the intersection is maximum.

$e.g: A=[(1,2),(1,4),(3,7),(4,7)]$

The maximum intersection is given by the elements $(3,7)$ and $ (4,7) $ with $4$ elements {4,5,6,7}.

The algorithm is required to be implemented using the Divide and Conquer strategy and running in time $O (n\log n) $.

Any ideas?

  • $\begingroup$ Do you have any ideas? How can you divide the input? $\endgroup$ – Yuval Filmus Jun 19 '17 at 0:16
  • $\begingroup$ Try doing divide and conquer with respect to inf or sup. $\endgroup$ – Yuval Filmus Jun 19 '17 at 0:23
  • $\begingroup$ How about first sorting with respect to $sup$, and then applying Divide and Conquer? How does Merge sort merge two arrays? $\endgroup$ – fade2black Jun 19 '17 at 0:29
  • $\begingroup$ My first approach was to order the intervals respect to inf or sup, then dividing it to half and calculating the maximum intersection of the middle element with the rest of the array. But I dont know what to do if the maximum int. Is given by two elements one in each side of the array. I thought about doing the same thing twice, sorting by inf and then by sup, but I dont think that works either. $\endgroup$ – Jessica Singer Jun 19 '17 at 2:01
  • $\begingroup$ After sorting according to $sup$, suppose you have an array of sorted intervals which equally split into two parts, left part and right part. And assume you have intervals $l_1, l_2$ and $r_1, r_2$ which are optimal solutions for the left subarray, and optimal solution for the right subarray respectively. I think we can generate the optimal solution out of four intervals $l_1, l_2, r_1, r_2$ for the given array. $\endgroup$ – fade2black Jun 19 '17 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.