LCC '21 Contest 6 S1 - Segment Intersection

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

Given N line segments, each with a starting and ending position on a number line, what is the maximum number of segments overlapped at a single point along the number line? A line segment is considered to overlap with a point if it starts before or on the point and ends after or on the point.

Input Specification

The first line will contain a single integer N (1 \leq N \leq 10^5), the number of segments.

The next N lines will contain two integers each, a_i (-10^{12} \leq a_i \leq 10^{12}) and b_i (a_i < b_i \leq 10^{12}), the starting and ending position of the i-th line segment.

Output Specification

Output a single integer, the maximum number of line segments overlapping at a single point along the number line.

Subtasks

Subtask 1 [20%]

-10^4 \leq a_i \leq 10^4

a_i \leq b_i \leq 10^4

Subtask 2 [80%]

No additional constraints.

Sample Input 1

5
1 2
2 4
3 6
4 7
1 3

Sample Output 1

3

Explanation for Sample 1

On points 3 and 4, the overlap of 3 line segments occurs.

Sample Input 2

10
1 100
3 20
18 21
11 12
12 13
11 12
1 4
4 5
5 6
7 8

Sample Output 2

5

Comments

There are no comments at the moment.