2
$\begingroup$

Let's say we have given $N$ intervals in the form $[x, y]$, both $x,y$ are integers , we want to find the number of integers covered by at least one interval of all $N$ intervals, (look in the example for better understand).

The intervals may or may not intersect.

Example: Let N = 3, and the intervals: $a_1 = [1, 5], a_2 = [3, 7], a_3=[5,7]$ The count of the integers is 7, because they cover the numbers: $1,2,3,4,5,6,7$

Is it possible to get such size in $O(N)$ time complexity

I tried to come up with solution but I think that we should sort the intervals in some way and then to search them in linear time, but I cannot think how should we make the search and how to sort them.

$\endgroup$
4
$\begingroup$

There is a simple $O(n\log n)$ algorithm based on sorting all the endpoints of the intervals. I will describe a more sophisticated algorithm, which outputs the union of the input intervals as a union of internally disjoint intervals (they may have overlapping endpoints). Denote the input intervals by $[s_i,t_i]$.

  • Initialize a variable $a$ to 0. This variable counts the number of active intervals.

  • Let $x$ go over the sorted order of the $s_i,t_i$:

    • If $x = s_i$ and $a = 0$, record $s_i$ as the starting point $s$ of the current interval.
    • If $x = s_i$ (regardless of $a$), increase $a$ by one.
    • If $x = t_i$, decrease $a$ by one. If now $a = 0$, output $[s,x]$.

It is not hard to modify this algorithm to output a union of truly disjoint intervals.

This algorithm runs in $O(n\log n)$, the running time being dominated by the cost of sorting the endpoints of the intervals. If the endpoints are integers and we can only access them using comparisons, then there is a simple $\Omega(n\log n)$ lower bound obtained by reduction from element uniqueness. Given a list of integers $x_1,\ldots,x_n$, form intervals $[3x_i,3x_i+1]$; I'll let you take it from here. This might look like cheating (since we assume that the endpoints are integers, and use arithmetic operations in the reduction), but it does rule out certain kinds of algorithms from achieving $o(n\log n)$ performance.

| cite | improve this answer | |
$\endgroup$

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.