Scheduling Maximum Non-Overlapping Tasks

Problem Description:

You are given a list of tasks, each represented by a start time and an end time in a 24-hour format. Your goal is to select the maximum number of tasks that do not overlap. Two tasks are considered non-overlapping if the start time of one is greater than or equal to the end time of the other.

Formally, each task is represented as a tuple \((s, e)\), where \(s\) is the start time and \(e\) is the end time. You need to choose a subset of these tasks such that for any two tasks \((s_i, e_i)\) and \((s_j, e_j)\) in this subset, either \(s_i \ge e_j\) or \(s_j \ge e_i\) holds. Output the maximum number of tasks that can be scheduled without overlapping.

inputFormat

The first line of input contains a single integer (n) representing the number of tasks. Each of the following (n) lines contains two space-separated integers denoting the start time and end time of a task.

outputFormat

Output a single integer representing the maximum number of non-overlapping tasks that can be scheduled.## sample

4
1 4
2 5
6 8
5 7

2