Ninja and his meetings
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

Question

Ninja and his meetings

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

Accepted Answer

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:

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’).

Space Complexity: O(n)Explanation:

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).

Time Complexity: O(2^n)Explanation:

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).

Accepted Answer

Memoization

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:
1. 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:
1. Return ‘MEMO[CURR_MEETING_NUMBER]’ .
Now Ninja has two choices, either he can schedule this meeting or skip this meeting:
1. ‘SCHEDULE_CURR_MEETING’ = ‘MEETINGS[CURR_MEETING_NUMBER]’ + MAX_MINUTES(‘MEETINGS’, currMeetingNumber + 2, MEMO).
2. ‘SKIP_CURR_MEETING’ = MAX_MINUTES(‘MEETINGS’, CURR_MEETING_NUMBER + 1, MEMO).
3. First, store in ‘MEMO’ the MAX(‘SCHEDULE_CURR_MEETING’, ‘SKIP_CURR_MEETING’) and then return ‘MEMO[CURR_MEETING_NUMBER]’.

Space Complexity: O(n)Explanation:

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

There are at most ‘N’ different functions stored in the recursion stack. We are also using a ‘MEMO’ array/list in which we store max minutes till now. Hence the overall space complexity is O(N).

Time Complexity: O(n)Explanation:

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

Because now we are using the ‘MEMO’ array to store the previously calculated results. Now there are no repeated function calls. So overall time complexity is O(N).

C++ (g++ 5.4)

/*

	Time complexity: O(N)

	Space complexity: O(N) 



	Where N represents the number of meetings.

*/



int maxMinutesHelper(vector& meetings, int n, int currMeeting, vector& memo) {



	if(currMeeting >= n) {

		return 0;

	}



	if(memo[currMeeting] != -1) {

		return memo[currMeeting] ;

	}



	int scheduleCurrMeeting = meetings[currMeeting] + maxMinutesHelper(meetings, n, currMeeting + 2, memo);

	int skipCurrMeeting = maxMinutesHelper(meetings, n, currMeeting + 1, memo);



	memo[currMeeting] = max(scheduleCurrMeeting, skipCurrMeeting);



	return memo[currMeeting];



	}





int maxMinutes(vector& meetings, int n) {

    vector memo(n, -1);

    return maxMinutesHelper(meetings, n, 0, memo);

    

}

Java (SE 1.8)

/*

	Time complexity: O(N)

	Space complexity: O(N) 



	Where N represents the number of meetings.

*/



public class Solution {



	public static int maxMinutesHelper(int meetings[], int n, int currMeeting, int memo[]) {



	if(currMeeting >= n) {

		return 0;

	}



	if(memo[currMeeting] != -1) {

		return memo[currMeeting] ;

	}



	int scheduleCurrMeeting = meetings[currMeeting] + maxMinutesHelper(meetings, n, currMeeting + 2, memo);

	int skipCurrMeeting = maxMinutesHelper(meetings, n, currMeeting + 1, memo);



	memo[currMeeting] = Math.max(scheduleCurrMeeting, skipCurrMeeting);



	return memo[currMeeting];



	}





    public static int maxMinutes(int meetings[], int n) {

        int memo[] = new int[n];

        for(int i = 0; i < n; i++) {

        	memo[i] = -1;

        }

        return maxMinutesHelper(meetings, n, 0, memo);

        

    }

}

Python (3.5)

'''
	Time complexity: O(N)
	Space complexity: O(N) 

	Where N represents the number of meetings.
'''

def maxMinutesHelper(meetings, n, currMeeting, memo):
    
    if currMeeting >= n:
        return 0
        
    if memo[currMeeting] != -1:
        return memo[currMeeting]
        
    scheduleCurrMeeting = meetings[currMeeting] + maxMinutesHelper(meetings, n, currMeeting + 2, memo)
    skipCurrMeeting = maxMinutesHelper(meetings, n, currMeeting + 1, memo)
    memo[currMeeting] = max(scheduleCurrMeeting, skipCurrMeeting)
    
    return memo[currMeeting]
    
def maxMinutes(meetings, n):
    
    memo = [-1] * n
    
    return maxMinutesHelper(meetings, n, 0, memo)

Accepted Answer

Dynamic Programming

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:
1. ‘SCHEDULE_CURR_MEETING’ = ‘MEETINGS[CURR_MEETING_NUMBER]’ + ‘DP[i+2]’.
2. ‘SKIP_CURR_MEETING’ = ‘DP[i+1]’.
3. ‘DP[i]’ = MAX(‘SCHEDULE_CURR_MEETING’, ‘SKIP_CURR_MEETING’)
Finally, return ‘DP[0]’.

Space Complexity: O(n)Explanation:

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

Because for finding our result we are using an extra ‘DP’ array/list. Hence the overall space complexity is O(N).

Time Complexity: O(n)Explanation:

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

Because we are traversing the ‘MEETINGS’ array/list only once. So overall time complexity is O(N).

Java (SE 1.8)

/*

	Time complexity: O(N)

	Space complexity: O(N) 



	Where N represents the number of meeting.

*/



public class Solution {



	public static int maxMinutes(int meetings[], int n) {

		int dp[] = new int[n + 2];



		for (int i = n - 1; i >= 0; i--) {

			int scheduleCurrMeeting = meetings[i] + dp[i + 2];

			int skipCurrMeeting = dp[i + 1];

			dp[i] = Math.max(scheduleCurrMeeting, skipCurrMeeting);

		}

		return dp[0];



	}

}

C++ (g++ 5.4)

/*

	Time complexity: O(N)

	Space complexity: O(N) 



	Where N represents the number of meeting.

*/



int maxMinutes(vector& meetings, int n) {

	vector dp(n + 2);



	for (int i = n - 1; i >= 0; i--) {

		int scheduleCurrMeeting = meetings[i] + dp[i + 2];

		int skipCurrMeeting = dp[i + 1];

		dp[i] = max(scheduleCurrMeeting, skipCurrMeeting);

	}

	return dp[0];



}

Python (3.5)

'''
	Time complexity: O(N)
	Space complexity: O(N) 

	Where N represents the number of meetings.
'''
    
def maxMinutes(meetings, n):
    
    dp = [0] * (n + 2)
    
    for i in range(n - 1, -1, -1):
        scheduleCurrMeeting = meetings[i] + dp[i + 2]
        skipCurrMeeting = dp[i + 1]
        dp[i] = max(scheduleCurrMeeting, skipCurrMeeting)
    
    return dp[0]

Accepted Answer

Iterative

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’.

Space Complexity: O(1)Explanation:

O(1)

Because we are not taking any extra space for finding our result.

Time Complexity: O(n)Explanation:

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

Because we are traversing the ‘MEETING’ array/list only once. So overall time complexity is O(N).

C++ (g++ 5.4)

/*

	Time complexity: O(N)

	Space complexity: O(1) 



	Where N represents the number of meeting.

*/



int maxMinutes(vector& meetings, int n) {

	int oneAway = 0;

	int twoAway = 0;



	for (int i = n - 1; i >= 0; i--) {

		int scheduleCurrMeeting = meetings[i] + twoAway;

		int skipCurrMeeting = oneAway;

		int temp = max(scheduleCurrMeeting, skipCurrMeeting);

		twoAway = oneAway;

		oneAway = temp;

	}

	return oneAway;



}

Python (3.5)

'''
	Time complexity: O(N)
	Space complexity: O(1) 

	Where N represents the number of meetings.
'''
    
def maxMinutes(meetings, n):
    oneAway = 0
    twoAway = 0
    
    for i in range(n - 1, -1, -1):
        scheduleCurrMeeting = meetings[i] + twoAway
        skipCurrMeeting = oneAway
        temp = max(scheduleCurrMeeting, skipCurrMeeting)
        twoAway = oneAway
        oneAway = temp
        
    return oneAway

Java (SE 1.8)

/*

	Time complexity: O(N)

	Space complexity: O(1) 



	Where N represents the number of meeting.

*/



public class Solution {



	public static int maxMinutes(int meetings[], int n) {

		int oneAway = 0;

		int twoAway = 0;



		for (int i = n - 1; i >= 0; i--) {

			int scheduleCurrMeeting = meetings[i] + twoAway;

			int skipCurrMeeting = oneAway;

			int temp = Math.max(scheduleCurrMeeting, skipCurrMeeting);

			twoAway = oneAway;

			oneAway = temp;

		}

		return oneAway;



	}

}

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:

Input Format

Output Format :

Note:

Constraints:

Top Atlassian Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern

Top HR questions asked in Atlassian Software Developer Intern