Minimum Machines Required

You are given a set of jobs where each job is represented by an interval \( [s, e] \) indicating its start time \( s \) and end time \( e \). Two jobs are said to overlap if their intervals intersect. Your task is to determine the minimum number of machines required to run all the jobs such that no two overlapping jobs are assigned to the same machine.

Note: An interval \( [s, e] \) means the job starts at time \( s \) (inclusive) and ends at time \( e \) (exclusive). Therefore, if one job ends at time \( t \) and another starts at \( t \), they do not conflict.

inputFormat

The input is given via standard input (stdin). The first line contains a single integer \( n \) representing the number of jobs. Each of the next \( n \) lines contains two space-separated integers \( s \) and \( e \), where \( s \) is the start time and \( e \) is the end time of a job.

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of machines required to schedule all the jobs without conflicts.

3
1 4
2 5
3 6

3