Maximum Non-overlapping Sessions

Problem Statement:

You are given (n) sessions, each represented by a start time (s_i) and an end time (e_i). Your task is to choose the maximum number of sessions that do not overlap. In other words, if you select a session with interval ((s_i, e_i)), then you cannot select another session whose start time is less than (e_i).

A common greedy algorithm can be employed to solve this problem: sort the sessions by their ending times in increasing order, and then iterate through the sorted sessions, selecting a session if its start time is at least the end time of the previously selected session.

Formally, given sessions represented by intervals ((s_i, e_i)), find the maximum number of sessions such that for any two sessions ((s_i, e_i)) and ((s_j, e_j)) with (s_i \leq s_j), it holds that (s_j \geq e_i).

inputFormat

The input is provided via standard input (stdin).

The first line contains a single integer (n) representing the number of sessions. Each of the following (n) lines contains two space-separated integers (s) and (e), which represent the start and end times of a session respectively.

outputFormat

Output a single integer to standard output (stdout) representing the maximum number of non-overlapping sessions that can be attended.## sample

3
1 4
2 3
3 5

2