Encontre um ponto compartilhado pelo máximo de segmentos

Dado: $N$ segmentos (matrizes) de números inteiros ordenados, números inteiros podem ser de $-K$ para $K$.

Exemplo:

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

Você pode representá-los como [min, max] --- é equivalente:

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

Como posso encontrar um número inteiro que pertença à quantidade máxima de segmentos? Para o exemplo dado, é 1.

Eu procuro o algoritmo mais eficiente.

Vamos usar $+$ para denotar o início de um segmento e $-$para denotar o fim. Para cada segmento, crie dois pares, um para cada terminal:

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

Classifique o $2N$pares pela primeira coordenada (em caso de igualdade, coloque + antes -). Você pode fazer isso a tempo$O(N \log N)$ com qualquer algoritmo de classificação razoável ou com o tempo $O(N + K)$usando contagem indexada por chave . No exemplo, obtemos:

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

Agora processe os pontos de extremidade em ordem. Mantenha uma contagem do número de segmentos ativos, que é inicialmente 0. Toda vez que você processa um$+$, aumente a contagem em 1. Toda vez que você processar um $-$, diminua a contagem em 1. Depois de processar cada nó de extremidade, verifique se a nova contagem é maior que a maior contagem até agora; se for, atualize sua solução.

(-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

Esta segunda fase do algoritmo leva tempo proporcional $N$. Todo o algoritmo leva tempo$O(N \log N)$ com uma classificação genérica ou $O(N + K)$ com contagem indexada por chave.

Vamos construir uma matriz de tamanho 2 * k + 1, todos inicializados com 0. Para cada segmento do formulário [L, R], adicionaremos 1 no L ^th index e subtrairemos 1 do R + 1 ^th index.

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

Agora, para obter o resultado, executaremos uma soma de prefixo.

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

Seja eu o índice com o valor máximo. Então a resposta será iK .
Vamos resolver o exemplo solicitado:

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.

A complexidade temporal da abordagem acima será O (máx (N, K)) .