0
$\begingroup$

Given a collection of non-empty intervals [a,b), where a/b are integers in some finite range (ex. 0...100) and a is less than b, can you find an algorithm that will detect all intervals that exhibit some collision/overlap where the worst-case performance of the algorithm is better than O(n^2)? You can assume that intervals starting at an end of another interval do not overlap, ex [15,22) and [22,30) do not overlap.

For example, given this collection {[12,16),[8,13),[16,34)} the result would be {0,1} because interval at index 0 intersects some interval, and interval at index 1 intersects some interval.

I have an algorithm that in worst case performs O(n^2) but can't figure out one that is faster. Mine doesn't use binary search trees, simply orders the intervals according to a, and then has a loop over all the elements with an inner loop on the remaining elements checking for intersection -- once an inner loop interval doesn't intersect the inner loop stops and the outer loop proceeds to the next element.

I am not looking for exact code, just a clear explanation of such an algorithm.

Improve this question
$\endgroup$
1
  • $\begingroup$ @D.W. This problem is derived from an interview I had 2 weeks ago. The original problem dealt with events having a start date and an end date. You could assume that each event falls within the boundry of a single day, but this assumption doesn't change the nature of the problem, as each day can be considered an individual subproblem. What I didn't realize at the time is that one could naturally assume that the start/end dates would abide to an HHMM format, ignoring seconds and milliseconds, so the problem could be reduced to a range of [0,2400). $\endgroup$
    – andrewz
    Sep 27 '20 at 20:09
1
$\begingroup$

As pointed out by the other answer, producing a list of the intersections is not doable in subquadratic time. However, counting all the intersections can be done in linear time. The rough idea for that one is to sort all coordinates (starting points and end points of intervals) into one list using counting sort (as the range of the values we are sorting is fixed) and iterate over it, maintaining a counter for the number of intervals intersecting at the current point and another one for the total number of intersections. If the current coordinate is an end point, reduce the first counter by 1. Otherwise (i.e. the current coordinate is a starting point), increase the first counter by 1 and increase the total counter by the value of the first counter.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Because of the sorting, this not linear but $\Theta(n\log n)$. $\endgroup$
    – Tassle
    Sep 27 '20 at 13:44
  • $\begingroup$ The range of values to be sorted is fixed, so counting sort can be used for sorting in linear time. $\endgroup$
    – Watercrystal
    Sep 27 '20 at 14:00
  • $\begingroup$ I missed that, sorry! $\endgroup$
    – Tassle
    Sep 27 '20 at 15:45
  • $\begingroup$ My apologies, my initial problem description was wrong, please read my edit. $\endgroup$
    – andrewz
    Sep 27 '20 at 19:55
  • $\begingroup$ This (can be used to) answer your revised question as well. $\endgroup$
    – D.W. ♦
    Sep 27 '20 at 21:23

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.