Meeting

Easy
0/40
Average time to solve is 15m
profile
Contributed by
18 upvotes
Asked in companies
BarclaysUberThought Works

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
2 1 4
0 1
2 3
Sample Output 1:
2
Explanation For Sample Output 1:
If we reschedule the second meeting from 2 to 1, then the duration from 2 to 4 will be free, and it is the longest among all possible answers.
Sample Input 2:
1
3 0 11
2 4
4 5
8 10
Sample Output 2:
3
Hint

Maximum sum subarray of size ‘K+1’.

Approaches (2)
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.
Time Complexity

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

Space Complexity

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

Code Solution
(100% EXP penalty)
Meeting
Full screen
Console