FastPrepFastPrep
Problem Brief

Max Sum of Non-Overlapping Intervals

FULLTIMEOA
See Amazon online assessment and hiring insights

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.

    1Example 1

    Input
    starts = [4, 2, 7, 8], durations = [3, 2, 3, 2], costs = [7, 3, 1, 2]
    Output
    9
    Explanation
    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.
    public int maxSumNonOverlappingIntervals(int[] starts, int[] durations, int[] costs) {
  // write your code here
}
    Input

    starts

    [4, 2, 7, 8]

    durations

    [3, 2, 3, 2]

    costs

    [7, 3, 1, 2]

    Output

    9

    Sign in to submit your solution.