Maximize Non-overlapping Intervals
MediumPractice library · +20 XPgreedysorting
Given N intervals, where each interval is defined by a start time and an end time, find the maximum number of non-overlapping intervals that can be selected. Two intervals [a, b] and [c, d] are considered non-overlapping if b <= c or d <= a. We assume intervals are closed, i.e., [a, b] includes both a and b.
Input
The first line contains an integer N, the number of intervals. The next N lines each contain two space-separated integers, representing the start and end times of an interval.
Output
Print a single integer: the maximum number of non-overlapping intervals that can be selected.
Constraints
1 <= N <= 200000 0 <= start_time <= end_time <= 10^9
Time limit 1 s (native code; slower languages get more)Memory 256 MB13 hidden tests
Example 1
Input
5 1 4 2 5 6 8 4 7 9 10
Output
3
Select (1,4), (6,8), (9,10). Total 3.
Example 2
Input
3 1 10 2 3 4 5
Output
2
Select (2,3), (4,5). Total 2.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 1 4 2 5 6 8 4 7 9 10
Example 2 input
3 1 10 2 3 4 5