Maximum Non-overlapping Banners

You are given n banners, each specified by its start and end positions. Your task is to determine the maximum number of banners that can be placed such that none of them overlap. Two banners are considered non-overlapping if the start position of a banner is greater than or equal to the end position of the previously selected banner.

Approach: This can be solved by a greedy algorithm. First, sort the banners by their end positions, and then iteratively choose banners that start after or exactly when the previous one ended.

Mathematical Formulation:

Let the sorted banners be \(b_1, b_2, \dots, b_n\) with each banner \(b_i = [s_i, e_i]\). Then, initialize \(currentEnd = -\infty\) and count = 0. For each banner, if \(s_i \geq currentEnd\) then include it and update \(currentEnd = e_i\). The final count is the maximum number of non-overlapping banners.

inputFormat

The first line contains an integer n, the number of banners. Each of the following n lines contains two integers representing the start and end positions of a banner, separated by a space.

Input Format:

n
s1 e1
...
sn en

outputFormat

Output a single integer which is the maximum number of non-overlapping banners that can be placed.

Output Format:

result

## sample

5
1 3
2 5
7 10
9 13
11 15

3