Internship experience

Moderate
0/80
Average time to solve is 35m
profile
Contributed by
5 upvotes
Asked in company
Microsoft

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1 :

2
0
3
5
2 2
0 1
1 1
1 2
3 5
2
4
6
0 1
0 2
0 3
2 5
3 3
5 5

Sample Output 1 :

8
18

Explanation for sample input 1 :

Test case 1:
The initial experience is 0 days. Alice can only do an internship in the second company
After completing the internship, she has 1 day of experience. Now she can do an internship in the fourth company and gain 2 days of experience.
After completing the internship, she has 3 days of experience. Now she can do an internship in the fifth company and gain 5 days of experience.
So the maximum experience she can gain after completing 3 internships is 8 days.

Test case 2:
The initial experience is 2 days. Alice can do an internship in any of the first 4 companies. 
She completes an internship in the fourth company and gains 5 days of experience.
Now she has 7 days of experience. She completes an internship in the sixth company and gains 5 days of experience.
Now she has 12 days of experience. She completes an internship in the fifth company and gains 3 days of experience.
Now she has 15 days of experience. She completes an internship in the third company and gains 3 days of experience.
So the maximum experience she can gain after completing 4 internships is 18 days.

Sample Input 2 :

1
0
2
3
1 2
1 3
1 4

Sample Output 2 :

0

Explanation for sample input 2 :

Test case 1:
Alice has an initial experience of 0 days. All the 3 companies require a minimum of 1 day of experience. Therefore she is not eligible to do an internship in any of the companies.
So the maximum experience she can gain is 0 days.
Hint

For all the ‘K’ internships, iterate over all the available companies. Among all the companies with a minimum experience requirement less than or equal to our current experience, we chose the company with maximum experience gain.

Approaches (2)
Brute Force

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 ‘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’.
Time Complexity

O(N * K), where ‘N’ is the number of companies in which Alice wants to do an internship, and ‘K’ represents the maximum number of internships Alice can complete.

 

For all the ‘K’ internships, we are iterating over all the ‘N’ companies. Therefore, the total time complexity will be O(K) *  O(N), which is O(N * K).

Space Complexity

O(N), where ‘N’ is the number of companies in which Alice wants to do an internship.

 

O(N) space is taken by ‘completed’ array to keep track of the available companies. So, the total space complexity will be O(N).

Code Solution
(100% EXP penalty)
Internship experience
Full screen
Console