Maximum Sum of Non-Overlapping Segments
You are given a list of N line segments on the number line. Each segment is defined by a start point and an end point. You want to select a subset of these segments such that no two selected segments overlap, and the sum of the lengths of the selected segments is maximized. If segments share an endpoint, they are considered non-overlapping. Segments are 1-indexed.
Input
The first line contains an integer N. The next N lines each contain two integers, the start point and end point of a segment.
Output
Print a single integer representing the maximum possible sum of lengths of non-overlapping segments.
Constraints
1 <= N <= 200000, 0 <= start_i <= end_i <= 10^9
Example 1
4 1 5 2 6 7 8 3 4
5
Segments are (1,5) len 4, (2,6) len 4, (7,8) len 1, (3,4) len 1. Sorted by end: (3,4) len 1, (1,5) len 4, (2,6) len 4, (7,8) len 1. We can pick (3,4) and (7,8) for total length 1+1=2. Or pick (1,5) and (7,8) for total length 4+1=5. Max length is 5.
Example 2
3 1 10 2 5 6 9
9
Segments are (1,10) len 9, (2,5) len 3, (6,9) len 3. Sorted by end: (2,5) len 3, (6,9) len 3, (1,10) len 9. We can pick (2,5) and (6,9) for total length 3+3=6. Cannot pick (1,10) with either (2,5) or (6,9). Max length is 6.
Hints
Similar problems
- Maximum Sum of Non-Adjacent SubarraysMedium
- Minimize Maximum Difference in PairsMedium
- Maximize Non-overlapping IntervalsMedium
- Maximum Sum of Non-Overlapping SubsegmentsMedium
- Max Consecutive SumMedium
- Maximum Sum of Non-Overlapping Positive SubarraysMedium
More topics: Sorting problems, 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 5 2 6 7 8 3 4
3 1 10 2 5 6 9