Ninja and his meetings

Moderate
0/80
Average time to solve is 20m
8 upvotes
Asked in companies
AmazonOracleIntuit

Problem statement

Ninja has recently started a startup. In his startup, there is only one conference room for a meeting. Ninja receives an array/list ‘MEETINGS’ of back-to-back appointment requests and is debating which ones to accept. Ninja needs a 15-minute break between appointments, and therefore he cannot accept any adjacent requests.

Ninja has to find the highest total booked minutes in the conference room for all meetings.

Note: All meeting timings are multiples of 15.

For example:

‘MEETINGS[]’ = {30, 15, 60}

Let us assume the meeting starts at 12:00 o’clock.
The first meeting takes 30 minutes so after the first meeting time is 12:30.
Then Ninja cannot attend the second meeting which is for 15 minutes because he needs 15 minutes break after every meeting.
After a 15 minutes break, he can attend the next meeting which is for 60 minutes.

So the total booked minutes for the meetings is 30 + 60 = 90.
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains an integer ‘N’ represents the number of meetings.

The next line of each test case contains ‘N’ single space-separated integers denoting the time taken by a meeting.
Output Format : 
For each test case, return the number of minutes for all meetings which are scheduled.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= ‘T’ <= 10^2
1 <= ‘N’ <= 5*10^3
0 <= ‘MEETINGS[i]’ <= 10^5 {each multiple of 15}

Time Limit: 1 second
Sample Input 1:
1
8
30 15 60 75 45 15 15 45
Sample Output 1:
180

Explanation for Sample Output 1:

For sample test case 1: 

Let’s assume the first meeting starts at 12:00 o’clock.
Then, the first meeting takes 30 minutes, so after the first meeting, the time is 12:30.
Then Ninja cannot attend the second meeting which is for 15 minutes because he needs a 15 minutes break after every meeting. So after a 15 minutes break, the time is 12:45.
Then he attends the third meeting which is for 60 minutes, so after the third meeting, the time is 13:45.
Now he cannot attend the fourth meeting which is for 75 minutes because he needs a 15 minutes break after every meeting. We know the fifth meeting starts after 75 minutes because the allocated time for the fourth meeting is 75 minutes. So after 75 minutes, the time is 15:00.
Then he attends the fifth meeting which is for 45 minutes, so after the third meeting, the time is 15:45.
Now he cannot attend the sixth meeting which is for 15 minutes because he needs a 15 minutes break after every meeting. So after a 15 minutes break, the time is 16:00.
Then he skips the seventh meeting also, which is for 15 minutes, so after the seventh meeting, the time is 16:15.
Then he attends the eighth meeting which is for 45 minutes, so after the eighth meeting, the time is 17:00.

So Ninja attended the first, third, fifth, eighth meeting. 
Hence the total minutes are: 30 + 60 + 45 + 45 = 180.
Sample Input 2:
1
4
60 15 15 60
Sample Output 2:
120

Explanation for Sample Output 2:

For sample test case 1: 

Let’s assume the first meeting starts at 12:00 o’clock.
Then, the first meeting takes 60 minutes, so after the first meeting, the time is 13:00.
Then he cannot attend the second meeting which is for 15 minutes because he needs 15 minutes to break after every meeting. So after a 15 minutes break, the time is 13:15.
Then he skips the third meeting also, which is for 15 minutes, so after the third meeting, the time is 13:30.
Then he attends the fourth meeting which is for 60 minutes, so after the fourth meeting, the time is 14:30.

So he attended the first and the fourth meeting.  
Hence the total minutes are: 60 + 60 = 120.
Hint

Think of the recursive approach.

Approaches (4)
Recursion

As we know if Ninja skips the previous meeting, then he has two choices for the current meeting, that is he can either schedule this meeting or he can skip this meeting.

If Ninja schedules the previous meeting, then he has only one choice that is he has to skip the current meeting.

 

Here is the algorithm:

  1. Base case: If the current meeting number is greater than the number of meetings:
    • Return 0.
  2. Now Ninja has two choices, either Ninja can schedule this meeting or skip this meeting:
    • ‘SCHEDULE_CURR_MEETING’ = ‘MEETINGS[CURR_MEETING_NUMBER]’ + MAX_MINUTES(‘MEETINGS’, CURR_MEETING_NUMBER + 2).
    • ‘SKIP_CURR_MEETING’ =  MAX_MINUTES(‘MEETINGS’, CURR_MEETING_NUMBER + 1).
    • Return MAX(‘SCHEDULE_CURR_MEETING’, ‘SKIP_CURR_MEETING’).
Time Complexity

O(2 ^ N) where ‘N’ represents the number of meetings.

 

Because at every meeting Ninja has two choices that are either he can schedule this meeting or skip this meeting. Hence the overall complexity is O(2 ^ N).

Space Complexity

O(N) where ‘N’ represents the number of meetings.

 

There are at most ‘N’ different function calls stored in the recursion stack. Hence the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Ninja and his meetings
Full screen
Console