FastPrepCinema Shows

Cinema Shows

Amazon logoAmazon● MediumFULLTIMEOA

Updated

Problem statement

A prominent media company (AMZ MGM) has partnered with select theaters to showcase exclusive video content, including feature films, episodic series, live performances, and more.

You are given an integer n, representing the number of scheduled screenings. Each screening has a start time, duration, and expected audience size, which are provided as integer arrays start, duration, and volume, respectively. Show i runs over the time interval [start[i], start[i] + duration[i]], and both end points belong to the show.

Your task is to determine the highest possible total audience size while ensuring that no two selected screenings overlap. Two screenings are considered non-overlapping if one fully concludes before the next one begins, that is, one show ends strictly before the other starts. For example, a show that ends at time 4 and a show that starts at time 4 overlap.

Function

cinemaShows(start: int[], duration: int[], volume: int[]) → int

Complete the function cinemaShows in the editor.

cinemaShows has the following parameters:

  1. int start[n]: an integer array denoting the start times of each show
  2. int duration[n]: an integer array denoting the durations of each show
  3. int volume[n]: an integer array denoting the volumes of each show

Returns int: an integer denoting the maximum possible volume that can be received

Examples

Example 1

start = [10, 5, 15, 18, 30]duration = [20, 12, 20, 35, 35]volume = [50, 51, 20, 25, 10]return = 76
Example 1 illustration

The shows run over [10, 30], [5, 17], [15, 35], [18, 53] and [30, 65]. Take show 2 ([5, 17]) and show 4 ([18, 53]). Show 2 ends at 17, which is before show 4 starts at 18, so they do not overlap. Their volume is 51 + 25 = 76. No other choice is better, for example show 1 and show 5 overlap because show 1 ends at 30, the time show 5 starts.

Example 2

start = [1, 2, 4]duration = [2, 2, 1]volume = [1, 2, 3]return = 4

The shows run over [1, 3], [2, 4] and [4, 5]. Take show 1 and show 3. Show 1 ends at 3, which is before show 3 starts at 4, so they do not overlap. Their volume is 1 + 3 = 4. Show 2 ends at 4, which is the time show 3 starts, so they overlap. Show 2 also overlaps show 1. So the answer is 4.

Constraints

  • 1 ≤ n ≤ 10^5
  • 1 ≤ start[i] ≤ 10^9
  • 1 ≤ duration[i] ≤ 10^9
  • 1 ≤ volume[i] ≤ 10^3

More Amazon interview questions

Similar questions at other companies

Interview reports that mention this question

Amazon interview experiences

See Amazon hiring insights
Saved
class Solution {
    public int cinemaShows(int[] start, int[] duration, int[] volume) {
      // write your code here
    }

}
Checking account…