Maximum Non-Overlapping Races

You are given a list of races, each defined by a pair of integers representing the start and end times. Your task is to select as many races as possible such that no two chosen races overlap.

Two races are considered non-overlapping if the start time of a race is strictly greater than the end time of the previously selected race. Formally, for two races with start and end times \( (s_i, f_i) \) and \( (s_j, f_j) \) where \( s_j \) is the start time of the race to be selected after the race ending at \( f_i \), the condition is:

[ s_j > f_i ]

Use a greedy algorithm by sorting races by their end times to achieve the solution efficiently.

inputFormat

The first number in the input is an integer \( M \) denoting the number of races. This is followed by \( 2 \times M \) integers where each pair represents the start and end times of a race.

Input Format:

M start1 end1 start2 end2 ... startM endM

outputFormat

Output a single integer representing the maximum number of non-overlapping races that can be selected.

3 1 2 2 3 3 4

2