Last Updated: 27 Mar, 2021
Meeting
Easy
Asked in companies
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
Approaches
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.
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’.
Similar problems