Maximum Sum of Non-Overlapping Intervals
Given N intervals, each with a start time and an end time, find a subset of non-overlapping intervals such that the sum of their lengths is maximized. Two intervals [a, b] and [c, d] are non-overlapping if b < c or d < a. Intervals are inclusive of their start and end times.
Input
The first line contains an integer N. The next N lines each contain two integers, the start time S and end time E of an interval.
Output
Print a single integer, the maximum possible sum of lengths of non-overlapping intervals.
Constraints
1 <= N <= 200000, 0 <= S <= E <= 10^9. The sum of lengths will fit in a 64-bit integer.
Example 1
4 1 3 2 5 6 8 7 9
7
Intervals are [1,3], [2,5], [6,8], [7,9]. Sorted by end time: [1,3], [2,5], [6,8], [7,9]. Max sum is from [1,3] (length 3) and [6,8] (length 3), total 6. Or [1,3] and [7,9] total 6. Or [2,5] and [6,8] total 3+3=6. Or [2,5] and [7,9] total 3+3=6. Max is 6.
Example 2
3 1 5 2 3 4 6
5
Intervals are [1,5], [2,3], [4,6]. Sorted by end time: [2,3], [1,5], [4,6]. Max sum is from [2,3] (length 2) and [4,6] (length 3), total 5.
Hints
Similar problems
- Longest Increasing Subsequence with Stack ConstraintHard
- Longest Increasing Subsequence on a PermutationHard
- Max Consecutive SumMedium
- Maximum Sum of Non-overlapping SubarraysMedium
- Maximum Sum of Adjacent ElementsEasy
- Longest Alternating SubsequenceMedium
More topics: Greedy problems, Dynamic Programming problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
4 1 3 2 5 6 8 7 9
3 1 5 2 3 4 6