Find a point shared by maximum segments

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.

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.

StackExchange Computer Science Q#105773, answer score: 11