Maximum Non-overlapping Intervals
Given a list of N intervals, where each interval is represented by a start time and an end time, find the maximum number of non-overlapping intervals that can be selected. Two intervals are considered overlapping if they share any common time, including endpoints. If two intervals end at the same time, only one can be chosen if they are to be considered non-overlapping with a subsequent interval. We want to maximize the count of selected intervals.
Input
The first line contains an integer N, the number of intervals. The next N lines each contain two integers, the start time and end time of an interval.
Output
Print a single integer representing the maximum number of non-overlapping intervals.
Constraints
1 <= N <= 200000, 0 <= start_i <= end_i <= 10^9
Example 1
5 1 3 2 4 3 5 4 6 5 7
3
Select intervals (1,3), (3,5), (5,7) for a total of 3.
Example 2
4 1 2 2 3 3 4 1 5
3
Select intervals (1,2), (2,3), (3,4) for a total of 3.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 1 3 2 4 3 5 4 6 5 7
4 1 2 2 3 3 4 1 5