Max Sum of Non-Overlapping Intervals
Problem statement
AMZ Interval Collection (A group of problems focused on operations involving intervals :) -
- Get Maximum Sum Find Overlapping Times (Full-Time)
- Find Overlapping Times (Intern)
- Merge Intervals (Intern, NG)
- Task Scheduler (Full-Time)
- Optimal Interval Difference
Given 3 arrays -
- Array 1 = Start times
- Array 2 = Durations
- Array 3 = Costs
Some intervals might overlap. Find the maximum sum of Non-Overlapping intervals.
Function
maxSumNonOverlappingIntervals(starts: int[], durations: int[], costs: int[]) → intExamples
Example 1
starts = [4, 2, 7, 8]durations = [3, 2, 3, 2]costs = [7, 3, 1, 2]return = 9Reason : Based on the given data, the intervals are [2,4], [4,7], [7,10] and [8,10] Non overlaping intervals are: [2,4],[7,10] and [4,7],[8,10] Considering [2,4] + [7,10] = 3 + 1 = 4, Considering [4,7] + [8,10] = 7 + 2 = 9 Answer is 9.