Maximum Non-overlapping Tasks

You are given a list of tasks, each defined by a start time and an end time. Your goal is to determine the maximum number of tasks that can be performed without any overlapping. Two tasks are considered non-overlapping if the start time of a task is not less than the end time of the previously selected task.

This problem can be modeled as an interval scheduling problem. Mathematically, for a set of intervals \([s_i, e_i]\), you must find the largest subset such that for any two intervals \([s_i, e_i]\) and \([s_j, e_j]\) (with \(e_i \le e_j\)) in the subset, \(s_j \ge e_i\) holds.

The recommended approach is to use a greedy algorithm where tasks are sorted by their ending times and then selected sequentially.

inputFormat

The input begins with an integer N, representing the number of tasks. This is followed by N lines, each containing two space-separated integers that represent the start time and the end time of a task.

outputFormat

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

3
1 3
2 5
4 6

2