Maximum Non-Overlapping Product Storages

You are given n products, each having a storage interval represented by a pair of integers \(l_i\) and \(r_i\) (the start and end of the storage period). The task is to find the maximum number of product storages you can choose so that none of them overlap.

An interval \([l_i, r_i]\) is considered non-overlapping with another interval \([l_j, r_j]\) if \(l_i > r_j\) or \(l_j > r_i\). You need to select the maximum count of such non-overlapping intervals.

Hint: A greedy strategy by sorting the intervals based on their ending times is a well-known approach to solve this problem optimally.

inputFormat

The input is given via standard input (stdin) in the following format:

 n
 l1 r1
 l2 r2
 ...
 ln rn

Here, n is the number of product storages, and each of the next n lines contains two integers representing the start \(l_i\) and end \(r_i\) of the storage interval.

outputFormat

Output a single integer to standard output (stdout) representing the maximum number of non-overlapping product storages that can be chosen.

4
1 6
2 8
3 5
7 9

2