Maximum Simultaneous Processes

You are given n processes. Each process is defined by its start time and end time. Your task is to determine the maximum number of processes that are running simultaneously at any moment.

More formally, given an integer \(n\) and \(n\) intervals \((s_i, e_i)\) where \(s_i\) is the start time and \(e_i\) is the end time of the \(i\)-th process, find the maximum number \(m\) such that there exists a time \(t\) for which exactly \(m\) processes are running concurrently.

Note: If a process ends at time \(t\) and another process starts at time \(t\), they are not considered to be running simultaneously.

The underlying idea can be explained using the sweep-line algorithm. For each process, consider two events: a start event and an end event. Sort these events by time; in case of a tie, process the end event first. Traverse the events and keep track of the current number of running processes, updating the maximum count as needed.

inputFormat

The first line contains an integer \(n\) (\(1 \leq n \leq 10^5\)), the number of processes.

Each of the following \(n\) lines contains two space-separated integers \(s_i\) and \(e_i\) (\(0 \leq s_i < e_i \leq 10^9\)), representing the start and end times of the \(i\)-th process.

outputFormat

Output a single integer which is the maximum number of processes running simultaneously.

5
1 5
2 6
4 8
3 7
5 9

4