Minimum Machines Required

You are given a set of tasks. Each task is represented by its start time and end time. The objective is to determine the minimum number of machines required to execute all tasks so that no two overlapping tasks are processed on the same machine.

Formally, you are given an integer n representing the number of tasks, followed by n lines where each line contains two integers start and end. A task is denoted by the interval [start, end]. Two tasks are considered overlapping if one task starts before the other has finished. Note that if one task ends exactly when another task starts, they do not overlap.

Example: Consider the tasks:

1 4
2 6
8 9
3 5
5 9

It is possible to process these tasks using 3 machines concurrently.

inputFormat

The input starts with an integer n (1 ≤ n ≤ 10⁵) representing the number of tasks. The following n lines each contain two integers start and end (1 ≤ start < end ≤ 10⁹) describing the start and end times of each task.

outputFormat

Output a single integer that is the minimum number of machines required to process all tasks without any overlapping on the same machine.

5
1 4
2 6
8 9
3 5
5 9

3