7
$\begingroup$

Given: $N$ segments (arrays) of ordered integers, integers could be from $-K$ to $K$.

Example:

Segment 1: [-2,-1,0,1,2,3]
Segment 2: [1,2,3,4,5]
Segment 3: [-3,-2,-1,0,1]

You can represent them as [min, max]---it is equivalent:

Segment 1: [-2,3]
Segment 2: [1,5]
Segment 3: [-3,1]

How can I find an integer that belongs to the maximum amount of segments? For the given example, it is 1.

I look for the most efficient algorithm.

$\endgroup$
11
$\begingroup$

Let's use $+$ to denote the start of a segment and $-$ to denote the end. For each segment, create two pairs, one for each endpoint:

Segment1: (-2, +), (3, -)
Segment2: (1, +), (5, -)
Segment3: (-3, +), (1, -)

Sort the $2N$ pairs by their first coordinate (in case of equality, put + before -). You can do this in time $O(N \log N)$ with any reasonable sorting algorithm, or in time $O(N + K)$ using key-indexed counting. In the example, we get:

(-3, +)
(-2, +)
(1, +)
(1, -)
(3, -)
(5, -)

Now process the endpoints in order. Maintain a count of the number of active segments, which is initially 0. Every time you process a $+$, increase the count by 1. Every time you process a $-$, decrease the count by 1. After processing each endpoint, check if the new count is higher than the largest count so far; if it is, update your solution.

(-3, +) -> count=1, max_count=0, sol=-3
(-2, +) -> count=2, max_count=1, sol=-2
(1, +) -> count=3, max_count=2, sol=1
(1, -) -> count=2, max_count=3, sol=1
(3, -) -> count=1, max_count=3, sol=1
(5, -) -> count=0, max_count=3, sol=1

This second phase of the algorithm takes time proportional $N$. The whole algorithm takes time $O(N \log N)$ with a generic sort, or $O(N + K)$ with key-indexed counting.

$\endgroup$
  • 1
    $\begingroup$ There is an alternative solution using segment trees. But the asymptotic cost is the same. $\endgroup$ – Vincenzo Mar 19 at 11:29
  • 1
    $\begingroup$ As endpoints are bounded integers, you even can skip the sort phase and just count the number of "in" and "out" on every position (4 K integers). $\endgroup$ – Vince Mar 19 at 13:44
  • $\begingroup$ @Vince you have to account for closed/open interval ends. That's what the 4 in 4 K is, I guess? $\endgroup$ – John Dvorak Mar 19 at 17:27
  • $\begingroup$ Thanks. My problem that the answer is looking like a voodoo. It does resolve the problem, but there is no explanation that could explain it properly. Tentatively, I explain it to myself by following: "going from left to right, we raise the count, finding common points, while more and more segments starting and adding to each other like a Union..; going from right to left we do the same, but raise the counter if this direction contains more common points than previous direction... ", but it is quite obsure why this "directions competition" brings the right result...Not easy... $\endgroup$ – Vladimir Nabokov Mar 20 at 8:15
  • $\begingroup$ @VladimirNabokov, the main idea is that in the second phase, the count variable at a given point equals the number of segments intersecting that point. By the way, there is only one traversal, from left to right. I think it will be easy to understand the algorithm if you first understand why it works for the cases of one segment only, and two segments only. $\endgroup$ – Vincenzo Mar 20 at 10:19
1
$\begingroup$

Let's build an array of size 2*k+1 all initialized with 0. For each segment of the form [L, R], we will add 1 at Lth index and subtract 1 from R+1th index.

Note : We add K to every values to shift the range from -K to +K to 0 to 2*K.

Now to obtain the result, we will perform a prefix sum.

array[i] = array[i-1] + array[i], where 1 <= i <= 2*K ( assuming 0-based indexing)

Let i be the index with maximum value. Then answer will be i-K.
Let us solve the asked example :

Let K = 5 and segments are [-2, 3], [1, 5] and [-3, 1]. Then after adding K the segments become
[3, 8], [6, 10] and [2, 6].
On performing the +1 and -1 updates our array will be
[0, 0, 1, 1, 0, 0, 1, -1, 0, -1, 0, -1].
Prefix sum will result into 
[0, 0, 1, 2, 2, 2, 3, 2, 2, 1, 1, 0].
Hence the index with max value is 6 and hence answer will be 6 - 5 = 1.

Time complexity of above approach will be O(max(N, K)).

$\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.