Last Updated: 4 Apr, 2021
Internship experience
Moderate
Asked in company
Alice has completed various courses on coding ninja, and now she is confident for her coding interviews. She plans to do internships in the summer and has prepared a list of ‘N’ companies. For each i-th company, the minimum experience needed is ‘minExp[i]’ days, and after completing the internship, she gains ‘expGained[i]’ days of experience. She is already having ‘D’ days of experience. As she is available only in summers, she can complete at most ‘K’ internships. Your task is to tell her the maximum experience(in days) she can gain after completing at most ‘K’ internships.
Note :
She cannot do more than one internship in the same company.
Input Format :
The first line of the input contains an integer ‘T’ representing the number of test cases.
The first line of each test case contains a single integer, ‘D’, where ‘D’ represents the amount of experience(in days) Alice has.
The second line of each test case contains a single integer, ‘K’, where ‘K’ denotes the maximum number of internships that Alice can complete.
The third line of each test case contains a single integer, ‘N’, where ‘N’ denotes the number of companies in which Alice wants to do an internship.
The next ‘N’ lines contain two space-separated integers, ‘minExp’ and ‘expGained’, where ‘minExp’ denotes the minimum experience(in days) needed, and ‘expGained’ denotes the experience(in days) gained after completion of the internship.
Output Format :
For each test case, print the maximum experience(in days) she can gain after completing at most ‘K’ internships.
The output of 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 <= 5
0 <= D <= 10 ^ 5
1 <= N <= 100
0 <= K <= N
0 <= minExp, expGained <= 10 ^ 5
Time Limit : 1 sec
Where ‘T’ is the number of test cases, ‘D’ is initial amount of experience, ‘N’ denotes the number of companies, ‘K’ represents the maximum number of internships Alice can complete, ‘minExp’ and ‘expGained’ denotes the minimum experience needed and experience gained after completing a particular internship respectively.
Approaches
The idea here is to keep track of all the available companies, i.e., the companies in which we haven’t done an internship. Among all such companies, we chose the company whose minimum experience requirement is less than or equal to our current experience and has the maximum experience gain as it is the most optimal choice.
Algorithm:
- Declare an integer, say ‘currExp’ to store the current amount of experience, and initialize it with ‘D’.
- Declare an array of booleans, say ‘completed’ to keep track of the companies in which we have completed an internship, and initialize each element of it with false.
- Run a loop for ‘K’ times.
- Declare a boolean variable, say ‘found’ to check whether we found any company or not, and initialize it with false.
- Declare an integer, say ‘maxGain’ to store the maximum experience gain, and initialize it with -1.
- Declare an integer, say ‘index’, to store the index of the company with maximum experience gain, and initialize it with -1.
- Run a loop for ‘i’ from 0 to ‘N’ - 1.
- If ‘completed[i]’ is false and ‘minExp[i]’ is less than or equal to ‘currExp’ and ‘expGained[i]’ is greater than ‘maxGain’:
- Update ‘maxGain’ as ‘maxGain’ = ‘expGained[i]’.
- Update ‘index’ as ‘index’ = ‘i’.
- Mark ‘found’ as true.
- If ‘completed[i]’ is false and ‘minExp[i]’ is less than or equal to ‘currExp’ and ‘expGained[i]’ is greater than ‘maxGain’:
- If ‘found’ is false.
- Break the loop, as we don’t have any available company to do an internship.
- Add ‘maxGain’ in ‘currExp’ i.e., do ‘currExp’ = currExp + maxGain.
- Mark ‘completed[index]’ as true.
- Return ‘currExp’.
The idea here is to sort the given companies in increasing order of their minimum experience requirement. Now we will iterate over all the companies from left to right and use a max - heap data structure to find a company with maximum experience gain among all the companies whose minimum experience requirement is less than or equal to our current experience.
Consider the example,
‘D’ = 2, ‘K’ = 4, ‘N’ = 7, ‘minExp’ = [ 2, 0, 0, 3, 5, 9, 7], ‘expGained’ = [ 0, 1, 5, 2, 3, 0, 4]
Firstly we will pair all the ‘minExp’ with their respective ‘expGained’, say ‘companies’
‘companies’ = [ [2, 0], [0, 1], [0, 5], [3, 2], [5, 3], [9, 0], [7, 4]]
Now we will sort ‘companies’ in increasing order of ‘minExp’, so that when we are at any i-th company, the minimum experience requirement for all the companies from 0 to i - 1 will be less than or equal to our current experience and hence we will be eligible to do an internship in any of the companies.
‘companies’ = [ [0, 1], [0, 5], [2, 0], [3, 2], [5, 3], [7, 4], [9, 0]]
As we need to maximize the total experience gain, we will use a Max - heap data structure to efficiently find the company with maximum experience gain among all the eligible companies. We will add the experience of that company and move to the next company.
After iterating the ‘companies’ from left to right, while ‘K’ is greater than 0, we will add the maximum element of the max-heap into ‘currExp’ and remove that element from the max - heap.
Algorithm:
- Declare an integer, say ‘currExp’ to store the current amount of experience, and initialize it with ‘D’.
- Declare a 2 - Dimensional array of integers, say ‘companies’ to store ‘minExp’ and ‘expGained’ of each company.
- Run a loop for ‘i’ from 0 to ‘N’ - 1.
- Insert [ ‘minExp[i]’, ‘expGained[i]’ ] into ‘companies’.
- Sort ‘companies’.
- Declare a max - heap of integers, say ‘maxHeap’, to find the maximum experience gain among all the eligible companies.
- Declare an integer ‘i’ to iterate through ‘companies’.
- Run a loop while ‘i’ is less than ‘N’ and ‘K’ is greater than 0.
- If ‘companies[i][0]’ is less than or equal to ‘currExp’:
- Insert ‘companies[i][1]’ into the ‘maxHeap’
- Increment ‘i’ i.e., do ‘i’ = i + 1.
- Else:
- If the ‘maxHeap’ is empty.
- Break the loop, as we cannot do an internship in any company.
- Add the maximum element of ‘maxHeap’ in ‘currExp’ and remove that element from the ‘maxHeap’.
- Decrement ‘K’ i.e., do ‘K’ = K - 1.
- If the ‘maxHeap’ is empty.
- If ‘companies[i][0]’ is less than or equal to ‘currExp’:
- Run a loop while ‘maxHeap’ is not empty and ‘K’ is greater than 0.
- Add the maximum element of ‘maxHeap’ in ‘currExp’ and remove that element from the ‘maxHeap’.
- Decrement ‘K’ i.e., do ‘K’ = K - 1.
- Return ‘currExp’.