Last Updated: 17 Mar, 2021
Ninja and his meetings
Moderate
Asked in companies
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.
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
Approaches
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:
- Base case: If the current meeting number is greater than the number of meetings:
- Return 0.
- 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’).
As we know in our previous approach there are a lot of repeating function calls. So we can optimize our recursive approach by using a ‘MEMO’ array/list. In ‘MEMO[i]’ we are storing the max minutes for all meetings till now.
Here is the algorithm:
- We declare a ‘MEMO’ array/list in which we store previously calculated results and initialize with -1.
- Finally, we return MAX_MINUTES_HELPER(‘MINUTES’, 0, ‘MEMO’).
MAX_MINUTES_HELPER(‘MINUTES’, 0, ‘MEMO’) function:
- Base case: If the current meeting number is greater than the number of meetings:
- Return 0.
- If the result for the current numbers of meetings is already calculated i.e. ‘MEMO[CURR_MEETING_NUMBER]’ is not equal to -1:
- Return ‘MEMO[CURR_MEETING_NUMBER]’ .
- Now Ninja has two choices, either he can schedule this meeting or skip this meeting:
- ‘SCHEDULE_CURR_MEETING’ = ‘MEETINGS[CURR_MEETING_NUMBER]’ + MAX_MINUTES(‘MEETINGS’, currMeetingNumber + 2, MEMO).
- ‘SKIP_CURR_MEETING’ = MAX_MINUTES(‘MEETINGS’, CURR_MEETING_NUMBER + 1, MEMO).
- First, store in ‘MEMO’ the MAX(‘SCHEDULE_CURR_MEETING’, ‘SKIP_CURR_MEETING’) and then return ‘MEMO[CURR_MEETING_NUMBER]’.
We can optimize our above approach by using a ‘DP’ array/list also. In ‘DP[i]’ we are storing the max minutes for all meetings till now.
Here is the algorithm:
- We declare a ‘DP’ array/list in which we store the max minutes for all meetings till now of size ‘N’ + 2 for avoiding the checking of the array out of bound condition.
- We run a loop for ‘i’ = ‘N’ - 1 to 0:
- ‘SCHEDULE_CURR_MEETING’ = ‘MEETINGS[CURR_MEETING_NUMBER]’ + ‘DP[i+2]’.
- ‘SKIP_CURR_MEETING’ = ‘DP[i+1]’.
- ‘DP[i]’ = MAX(‘SCHEDULE_CURR_MEETING’, ‘SKIP_CURR_MEETING’)
- Finally, return ‘DP[0]’.
We know Ninja can not accept any adjacent requests. Using this fact, we can optimize our above solution. For finding the highest total booked minutes till now we have only two ways:
- We include the current meeting. Then we need the highest total booked minutes till one meeting less than the current meeting.
- We do not include the current meeting. Then we need the highest total booked minutes till two meetings less than the current meeting.
Here is the algorithm:
- We declare two variables ‘ONE_AWAY’ and ‘TWO_AWAY’ in which we store the highest total booked minutes till one meeting less than the current meeting and two meetings less than the current meeting respectively.
- We run a loop for ‘i’ = ‘N’ - 1 to 0:
- ‘SCHEDULE_CURR_MEETING’ = ‘MEETINGS[CURR_MEETING_NUMBER]’ + ‘TWO_AWAY’.
- ‘SKIP_CURR_MEETING’ = ‘ONE_AWAY’.
- ‘TEMP’ = MAX(‘SCHEDULE_CURR_MEETING’, ‘SKIP_CURR_MEETING’).
- ‘TWO_AWAY’ = ‘ONE_AWAY’.
- ‘ONE_AWAY’ = ‘TEMP’.
- Finally, we return ‘ONE_AWAY’.
Similar problems