Meeting
Ninja is organizing a meeting in an office that starts at a time ‘0’ and will end at a time ‘LAST’. There are ‘N’ presentations that are going to take place in that meeting whose start and end times are given, i.e., ‘ith’ presentation starts at ‘START[i]’ and ends at ‘END[i]’. The presentations don’t overlap with each other. Ninja wants to reschedule at most ‘K’ presentations keeping the original order intact so that the longest period in which there is no presentation scheduled during the meeting is maximized.

Since Ninja is busy with other office work, your task is to help Ninja to reschedule at most ‘K’ presentations.

Note:

The presentation’s duration can’t be changed. You can only change the start and end times.

Input Format:

The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow. The first line of each test case contains three positive integers, ‘N’, ‘K’, and ‘LAST’, as described in the problem statement. The following ‘N’ line of each test case contains two non-negative integers denoting ‘start’ and ‘end’ time of ith presentation.

Output Format:

For each test case, print the duration of the longest period in which there is no presentation scheduled during the meeting after rescheduling, not more than ‘K’ meetings. Output for each test case will be printed 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

Meeting

Ninja is organizing a meeting in an office that starts at a time ‘0’ and will end at a time ‘LAST’. There are ‘N’ presentations that are going to take place in that meeting whose start and end times are given, i.e., ‘ith’ presentation starts at ‘START[i]’ and ends at ‘END[i]’. The presentations don’t overlap with each other. Ninja wants to reschedule at most ‘K’ presentations keeping the original order intact so that the longest period in which there is no presentation scheduled during the meeting is maximized.

Since Ninja is busy with other office work, your task is to help Ninja to reschedule at most ‘K’ presentations.

Note:

The presentation’s duration can’t be changed. You can only change the start and end times.

Input Format:

The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow. 

The first line of each test case contains three positive integers, ‘N’, ‘K’, and ‘LAST’, as described in the problem statement.

The following ‘N’ line of each test case contains two non-negative integers denoting ‘start’ and ‘end’ time of ith presentation.

Output Format:

For each test case, print the duration of the longest period in which there is no presentation scheduled during the meeting after rescheduling, not more than ‘K’ meetings.

Output for each test case will be printed 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
1 <= N <= 5000
0 <= K <= N
0 <= LAST <= 10^9
START[i] < END[i], for 1 <= i <= N.
END[i] <= START[i+1], for 1 <= i < N.

Time Limit: 1 second

Accepted Answer

Brute Force Approach

Algorithm:

The idea here is to find the maximum sum subarray of size ‘K+1’, where the array will contain empty slots.
First, we create an array named emptySlots[], to store the time duration in which there is no presentation.
Run a loop to traverse all presentations, and in each iteration, add START[i] - END[i-1] (which gives a free slot between the ith presentation) into the array emptySlots[].
Now, for each element, we have to calculate the sum of a subarray of size at most K + 1 starting from that element itself.
Create a variable named ‘ans’ to store the final answer, and initialize it with 0.
Run a loop from i = 0 to i = size of emptySlots[], in each iteration:
- Create a variable named ‘sum’ to store the sum of the subarray starting from the ith element.
- Again run a loop from j = i to j < i + (K+1) and size of emptySlots[], in each iteration do:
  - Add the jth element of emptySlots[] to the ‘sum’.
- If the sum is greater than ‘ans’, then update the ‘ans’.
In this way, we are calculating all subarray sum and updating ‘ans’ with the maximum of this. So, the value of variable ‘ans’ is our required answer.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of the presentations.

As we are using an extra array to store the empty slots, which can go up to the size ‘N’. Hence, space complexity will be O(N).

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the number of the presentations.

We are calculating the subarray sum of all subarray of size K + 1. So for each element, we are calculating the subarray sum. As calculating subarray sum it takes O(N) time, and for each element, it will go to O(N^2).

Java (SE 1.8)

/*

    Time Complexity     :   O(N ^ 2)

    Space Complexity    :   O(N)



    Where 'N' is the number of the presentations.

*/



import java.util.ArrayList;



public class Solution {

	public static int maxInterval(int t, ArrayList start, ArrayList end, int k) {

		

		// Create an ArrayList to store the time duration in which there is no presentation.

		ArrayList emptySlots = new ArrayList<>();



		// Fill the ArrayList 'emptySlots'.

		int prevEnd = 0;



		for (int i = 0; i < start.size(); i++) {

			emptySlots.add(start.get(i) - prevEnd);

			prevEnd = end.get(i);

		}



		emptySlots.add(t - prevEnd);

		int len = emptySlots.size();



		// Declare a variable to store the final answer.

		int ans = 0;



		// Find the subarray sum of all subarray of size K + 1.

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

		

			// Create a variable to store the sum of current subarray.

			int sum = 0;



			for (int j = i; j < len && j < i + (k + 1); j++) {

				sum += emptySlots.get(j);

			}



			// Update 'ans' with the maximum.

			ans = Math.max(ans, sum);

		}



		return ans;

	}

}

Python (3.5)

"""

    Time Complexity     :   O(N ^ 2)

    Space Complexity    :   O(N)



    Where 'N' is the number of the presentations.

"""



def maxInterval(t, start, end, k):



	# Create a list to store the time duration in which there is no presentation.

	emptySlots = []



	# Fill the list 'emptySlots'.

	prevEnd = 0



	for i in range(len(start)):

		emptySlots.append(start[i] - prevEnd)

		prevEnd = end[i]



	emptySlots.append(t - prevEnd)

	length = len(emptySlots)



	# Declare a variable to store the final answer.

	ans = 0



	# Find the subarray sum of all subarray of size K + 1.

	for i in range(length):



		# Create a variable to store the sum of current subarray.

		sum = 0

		for j in range(i, min(length, (i + k + 1))):

			sum += emptySlots[j]



		# Update ans with the maximum.

		ans = max(ans, sum)



	return ans

C++ (g++ 5.4)

/*

    Time Complexity     :   O(N ^ 2)

    Space Complexity    :   O(N)



    Where 'N' is the number of the presentations.

*/



int maxInterval(int t, vector &start, vector &end, int k) {



	// Create a vector to store the time duration in which there is no presentation.

	vector emptySlots;



	// Fill the vector 'emptySlots'.

	int prevEnd = 0;



	for (int i = 0; i < start.size(); i++) {

		emptySlots.push_back(start[i] - prevEnd);

		prevEnd = end[i];

	}



	emptySlots.push_back(t - prevEnd);

	int len = emptySlots.size();



	// Declare a variable to store the final answer.

	int ans = 0;



	// Find the subarray sum of all subarray of size K + 1.

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

		

		// Create a variable to store the sum of current subarray.

		int sum = 0;



		for (int j = i; j < len && j < i + (k + 1); j++) {

			sum += emptySlots[j];

		}



		// Update 'ans' with the maximum.

		ans = max(ans, sum);

	}



	return ans;

}

Accepted Answer

Sliding Window Approach

Algorithm:

The idea here is the same to approach 1, i.e., to find the maximum sum subarray of size ‘K + 1’, where the array will contain empty slots.
First, we create an array named emptySlots[], to store the time duration in which there is no presentation.
Run a loop to traverse all presentations, and in each iteration add START[i] - END[i-1] (which gives free slot between the ith presentation) into the array emptySlots[].
Now, unlike approach 1, we are not going to run a loop for each element. But here, we are using a window of size ‘K + 1’ at every iteration. We keep adding elements at the front while removing elements from the back.
Create a variable named ‘ans’ to store the final answer, and initialize it with 0.
Also, declare a variable named ‘sum’, and initialize it with 0.
Run a loop from i = 0 to i < K+1 and size of emptySlots[]:
- Add the ith element to the variable ‘sum’.
Update ‘ans’ with ‘sum’.
Now again run a loop from i = K+1 to i < size of emptySlots[], in each iteration do:
- Remove the (i - (K+1))th element from the ‘sum’.
- And add the ith element to the ‘sum’.
- Update ‘ans’ if it is less than the ‘sum’.
Finally, return the ‘ans’.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of the presentations.

As we are using an extra array to store the empty slots, which can go up to the size 'N'. Hence, space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of the presentations.

We are calculating the subarray sum of all subarray of size K + 1 by using the window. Every time we add the element at the front and remove an element from the back. Hence, the overall time complexity will be O(N).

Java (SE 1.8)

/*

    Time Complexity     :   O(N)

    Space Complexity    :   O(N)



    Where 'N' is the number of the presentations.

*/



import java.util.ArrayList;



public class Solution {

	public static int maxInterval(int t, ArrayList start, ArrayList end, int k) {



		// Create an ArrayList to store the time duration in which there is no presentation.

		ArrayList emptySlots = new ArrayList<>();



		// Fill the ArrayList 'emptySlots'.

		int prevEnd = 0;



		for (int i = 0; i < start.size(); i++) {

			emptySlots.add(start.get(i) - prevEnd);

			prevEnd = end.get(i);

		}



		emptySlots.add(t - prevEnd);

		int len = emptySlots.size();



		// Declare a variable to store the final answer.

		int ans = 0;

	

		// Declare a variable to store the sum of current window.

		int sum = 0;

	

		// Find the sum of 1st K + 1 window.

		for (int i = 0; i < k + 1 && i < len; i++) {

			sum = sum + emptySlots.get(i);

		}



		// Update 'ans'.

		ans = sum;



		// Find the sum of all K + 1 window and update 'ans' with the maximum.

		for (int i = k + 1; i < len; i++) {

			sum = sum - emptySlots.get(i - (k + 1)) + emptySlots.get(i);

			ans = Math.max(sum, ans);

		}



		return ans;

	}

}

Python (3.5)

"""

    Time Complexity     :   O(N)

    Space Complexity    :   O(N)



    Where 'N' is the number of the presentations.

"""



def maxInterval(t, start, end, k):



	# Create a list to store the time duration in which there is no presentation.

	emptySlots = []



	# Fill the list 'emptySlots'.

	prevEnd = 0



	for i in range(len(start)):

		emptySlots.append(start[i] - prevEnd)

		prevEnd = end[i]



	emptySlots.append(t - prevEnd)

	length = len(emptySlots)



	# Declare a variable to store the fianl answer.

	ans = 0



	# Declare a variable to store the sum of current window.

	sum = 0



	# Find the sum of 1st K + 1 window.

	for i in range(min(k + 1, length)):

		sum = sum + emptySlots[i]



	# Update 'ans'.

	ans = sum



	# Find the sum of all K + 1 window and update ans with the maximum.

	for i in range(k + 1,length):

		sum = sum - emptySlots[i - (k + 1)] + emptySlots[i]

		ans = max(sum, ans)



	return ans

C++ (g++ 5.4)

/*

    Time Complexity     :   O(N)

    Space Complexity    :   O(N)



    Where 'N' is the number of the presentations.

*/



int maxInterval(int t, vector &start, vector &end, int k) {



	// Create a vector to store the time duration in which there is no presentation.

	vector emptySlots;



	// Fill the vector 'emptySlots'.

	int prevEnd = 0;



	for (int i = 0; i < start.size(); i++) {

		emptySlots.push_back(start[i] - prevEnd);

		prevEnd = end[i];

	}



	emptySlots.push_back(t - prevEnd);

	int len = emptySlots.size();



	// Declare a variable to store the final answer.

	int ans = 0;

	

	// Declare a variable to store the sum of current window.

	int sum = 0;

	

	// Find the sum of 1st K + 1 window.

	for (int i = 0; i < k + 1 && i < len; i++) {

		sum = sum + emptySlots[i];

	}



	// Update 'ans'.

	ans = sum;



	// Find the sum of all K + 1 window and update 'ans' with the maximum.

	for (int i = k + 1; i < len; i++) {

		sum = sum - emptySlots[i - (k + 1)] + emptySlots[i];

		ans = max(sum, ans);

	}



	return ans;

}

Since Ninja is busy with other office work, your task is to help Ninja to reschedule at most ‘K’ presentations.

Note:

Input Format:

Output Format:

Note:

Constraints:

Top Cvent Software Developer interview questions & answers

Popular interview questions of Software Developer