To solve this problem, we need to find the maximum sum of weights from a set of non-overlapping intervals. The solution involves dynamic programming (DP) combined with binary search to efficiently determine non-overlapping intervals.
Approach
- Sort Intervals: First, sort all intervals by their end times. This helps in efficiently finding the latest non-overlapping interval using binary search.
- Binary Search for Non-overlapping Intervals: For each interval, find the latest interval that ends before the start of the current interval. This is done using binary search on the end times of the sorted intervals.
- Dynamic Programming: Use a DP array where
dp[i]represents the maximum sum of weights up to the i-th interval. For each interval, we have two choices:- Take the interval: Add its weight to the maximum sum of non-overlapping intervals before it.
- Skip the interval: Keep the maximum sum from the previous interval.
Solution Code
import bisect
def max_non_overlapping_sum(intervals):
if not intervals:
return 0
# Sort intervals by their end time
intervals.sort(key=lambda x: x[1])
n = len(intervals)
ends = [interval[1] for interval in intervals]
dp = [0] * n
# Base case: first interval
dp[0] = intervals[0][2]
for i in range(1, n):
start, end, weight = intervals[i]
# Find the latest interval that ends before current start
j = bisect.bisect_right(ends, start, 0, i) - 1
# Calculate sum if we take current interval
take = weight
if j != -1:
take += dp[j]
# Calculate sum if we skip current interval
skip = dp[i-1]
# Update dp[i] with the maximum of take or skip
dp[i] = max(take, skip)
return dp[-1]
# Example usage:
# intervals = [(start, end, weight)]
# print(max_non_overlapping_sum(intervals))
Explanation
- Sorting: By sorting intervals based on their end times, we ensure that we can use binary search to quickly find the latest non-overlapping interval.
- Binary Search: The
bisect_rightfunction helps find the insertion point of the current interval's start time in the list of end times of previous intervals. This gives us the index of the last non-overlapping interval. - DP Calculation: For each interval, we decide whether to take it (adding its weight to the sum of the last non-overlapping interval) or skip it (keeping the sum from the previous interval). The maximum of these two choices is stored in
dp[i].
This approach efficiently computes the maximum sum with a time complexity of O(n log n) (due to sorting and binary search), which is optimal for this problem. The space complexity is O(n) for storing the DP array and end times.
Note: This solution assumes the input intervals are in the form of tuples (start, end, weight). Adjust the input format as needed based on the actual problem's input structure. If the image had specific details (like different input parameters), the code could be modified accordingly, but this approach is general for non-overlapping interval sum maximization.


作者声明:本文包含人工智能生成内容。