Maximum Non-overlapping Performances

Tracy wants to attend as many performances as possible. Each performance is characterized by its start time and end time. Two performances are considered non-overlapping if the start time of one is not earlier than the end time of another that was already attended.

Given the total number of performances \(n\), along with two lists representing the start times and end times respectively, determine the maximum number of non-overlapping performances that Tracy can attend.

Hint: A greedy strategy works well for this problem. Sort the performances by their end times in ascending order. Then, select a performance if its start time is not smaller than the end time of the last selected performance.

inputFormat

The input is given in three lines from standard input (stdin):

• The first line contains a single integer \(n\) which represents the number of performances.
• The second line contains \(n\) space-separated integers representing the start times.
• The third line contains \(n\) space-separated integers representing the end times.

outputFormat

Output a single integer to standard output (stdout) - the maximum number of non-overlapping performances that Tracy can attend.

4
1 3 0 5
2 4 6 7

3