Maximum Number of Non-Overlapping Tasks

Given a list of tasks represented by their start and end times, your job is to determine the maximum number of non-overlapping tasks that can be completed in a single day by one worker.

Formally, you are given tasks with start times (s_i) and end times (e_i). The goal is to select the largest possible subset of tasks such that for any two chosen tasks ( (s_i, e_i) ) and ( (s_j, e_j) ) (with (i \neq j)), the condition (s_j \ge e_i) holds when the tasks are sorted by their finishing times. This is a classic greedy algorithm problem often referred to as the activity selection problem.

inputFormat

The input is provided via standard input (stdin). The first line contains an integer (n) representing the number of tasks. Each of the following (n) lines contains two space-separated integers (s) and (e) which denote the start and end times of a task, respectively.

outputFormat

Print a single integer to standard output (stdout) representing the maximum number of non-overlapping tasks that can be completed.## sample

4
1 3
2 5
3 9
6 8

2