Maximum Non-Overlapping Lectures

You are given n lectures, each with a start time and an end time. Your task is to determine the maximum number of lectures that can be conducted in one classroom without overlapping. Two lectures are considered overlapping if one lecture starts before the previous lecture ends.

Formally, let the lectures be represented as intervals \([s_i, e_i]\) for \(i=1,2,\dots,n\). We say that two lectures \([s_i, e_i]\) and \([s_j, e_j]\) do not overlap if \(s_j \ge e_i\) (after sorting by their end times). The goal is to select the maximum size set of non-overlapping lectures.

Hint: A greedy approach by sorting the intervals according to their end times is suitable for this problem.

inputFormat

The first line contains a single integer n denoting the number of lectures.

Each of the following n lines contains two space-separated integers s and e, representing the start and end times of a lecture respectively.

It is guaranteed that all times are integers. If n is 0, then no lectures are given.

outputFormat

Output a single integer representing the maximum number of non-overlapping lectures that can be scheduled in one classroom.

5
1 3
2 5
4 6
6 8
5 7

3