FastPrepFastPrep
Problem Brief

Get Max Programs

NEW GRADOA
See Amazon online assessment and hiring insights

Within an Amazon software management tool, there's a collection of software programs and time slots. Each time slot lasts k seconds, and within that time the slots do not overlap. The software programs are required to sequentially from 1 to n, and cannot be interrupted. Each program has a specific execution time denoted as time[i].

The objective is to execute the software programs following a specific algorithm:

  • Start with the first time slot.
  • Proceed sequentially through the software programs from left to right.
  • Execute a program if it can be completed within the current time slot (i.e., the remaining time in the time slot is greater than or equal to the execution time of the program).
  • If a program cannot be completed in the current time slot, move it to the next available time slot (if one is available).
  • Continue this process until the available time slot.
  • If there are no available time slots and some software programs remain to be executed, then the goal is to determine the maximum number of software programs that can be executed using this algorithm.

    • The goal is to determine the maximum number of software programs that can be executed using this algorithm. This can be done by moving to the last program executed within the set of software programs and removing the software programs from the leftmost of the list until the remaining set of software programs can be executed with the available time slots.

    Find the maximum number of software programs from the suffix that can be executed efficiently using this algorithm. In other words, you are looking for the longest sequence of consecutive software programs from the end of the list that can be successfully scheduled within the given time slots when scheduled according to the rules provided.

    Function Description

    Complete the function getMaxPrograms in the editor.

    getMaxPrograms has the following parameters:

    1. int time[n]: an array of integers denoting the execution time of software programs.
    2. int m: number of time slots available
    3. int k: time length of each time slot

    Returns

    int: the maximum number of software programs from the suffix that can be executed.

    🌷ଓ༉ Many thanks, HxyJxy, Nachos and spike! 🫡

    1Example 1

    Input
    time = [5, 2, 1, 4, 2], m = 2, k = 6
    Output
    4
    Explanation
    Firstly, you try to execute all the 5 software programs.
  • 1st software program will be executed in the first time slot.
  • Since only 1 minute is remaining in the first time slot, 2nd software program will be executed in the second time slot.
  • Now 4 minutes remain in this time slot, so the 3rd software program will be executed in this time slot.
  • Now 3 minutes are remaining in this time slot, but the next software program requires 4 minutes which requires another time slot that is not available.
    • So this set of programs starting from the first program can not be executed. Now you remove the first software program and try to execute the remaining 4 software programs i.e. [2, 1, 4, 2]
  • 1st software program will be executed in the first time slot.
  • Now 4 minutes are remaining in the first time slot, so the 2nd software program will be executed in this time slot.
  • Now 3 minutes are remaining in the first time slot, but the next software program requires 4 minutes which requires another time slot.
  • So, 3rd software program will be executed in the second time slot.
  • Now, 2 minutes are remaining in this time slot in which the last program will get executed.
    • So, all the software programs are executed in this set, hence, the answer is 4.

    2Example 2

    Input
    time = [4, 2, 3, 4, 1], m = 1, k = 4
    Output
    1
    Explanation
    Since there is only one time slot, of length 4, we can not start from the 1st, 2nd, 3rd, or 4th software program. Only the last software program will be executed. Hence the answer is 1.

    3Example 3

    Input
    time = [1, 2, 3, 1, 1], m = 3, k = 3
    Output
    5
    Explanation
    All the software programs will be executed in the following manner:
  • 1st and 2nd software programs in the first time slot.
  • 3rd software program in the second time slot.
  • 4th and 5th software programs in the third time slot.
    • Hence the answer is 5.

    Constraints

    Limits and guarantees your solution can rely on.

  • 1 ≤ n, m ≤ 2*105
  • 1 ≤ k ≤ 109
  • 1 <= time[i] <= k/li> 
    • public int getMaxPrograms(int[] time, int m, int k) {
  // write your code here
}
    Input

    time

    [5, 2, 1, 4, 2]

    m

    2

    k

    6

    Output

    4

    Sign in to submit your solution.