FastPrep
Problem · Intervals

Max Sum of Non-Overlapping Intervals

Learn this problem
● MediumAmazonFULLTIMEOA
See Amazon hiring insights

Problem statement

AMZ Interval Collection (A group of problems focused on operations involving intervals :) -

1. Get Maximum Sum Find Overlapping Times (Full-Time)

2. Find Overlapping Times (Intern)

3. Merge Intervals (Intern, NG)

4. Task Scheduler (Full-Time)

5. 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[]) → int

    Examples

    Example 1

    starts = [4, 2, 7, 8]durations = [3, 2, 3, 2]costs = [7, 3, 1, 2]return = 9
    Reason : 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.

    More Amazon problems

    drafts saved locally
    public int maxSumNonOverlappingIntervals(int[] starts, int[] durations, int[] costs) {
  // write your code here
}
    starts[4, 2, 7, 8]
    durations[3, 2, 3, 2]
    costs[7, 3, 1, 2]
    expected9
    checking account