Click here to Skip to main content
15,117,830 members
Please Sign up or sign in to vote.
1.27/5 (6 votes)
See more:
You want to hire some employees. There are N employees in total and each has skill U and wants salary V.

These employees are not independent and have made some groups. Thus, there are Q statements each stating that X and Y belong to the same group. If you want to hire a person then, his entire group must be hired. You have a budget B, you want to hire employees such that you get the maximum possible skill within the budget.

Input Format:

First-line contains T, the number of test cases. Each test case has: First an integer N to denote the number of skills and their salary V Next N lines follow each representing 2 integers U and V (skill and salary) Then we have an integer Q denoting the number of queries Q lines follow representing 2 integers X and Y Last line contains an integer denoting budget B Output Format:

Print a single integer representing the maximum number of skills that can be hired by Monk.

Print 0, if no one can be hired

Constraints:

1<=N,Q<=1000 1<=U<=1000 
Sample Input:

2
5
1 1
2 1
3 1
4 1
5 1
2
1 2
2 3
3
7
1 1
2 2 
3 3
4 2
10 12
12 90
5 8
3
1 2
4 12
2 12
100

In the first case we have the following;

Group   # Employees Cost
[1,2,3] 3   3
[4] 1   1
[5] 1   1
Thus, the maximum employees we can choose are 3 for a cost <= 3 (budget is 3)

In the second case:

Group   # Employees Cost
[1,2,4,12]  4   95
[3] 1   3
[10]    1   12
[5] 1   8
The best we can do with a budget of 100 is to pick 5 employees at a cost of 98

Sample input:

3
5
1 1
2 1
3 1
4 1
5 1
2
1 2
2 3
3
8
10 10
3 20
2 40
7 39
8 24
5 23
6 35
4 50  
3
5 7
6 8
5 6 
240
7
1 1
2 2 
3 3
4 2
10 12
12 90
5 8
3
1 2
4 12
2 12
100
Sample Output:

3
7
5
I'm not able to solve it, Any help would be appreciated! Thanks :)


What I have tried:

I'm not asking for a direct solution,
can you explain to me the logic, I'm not able to understand the question something like in layman's terms.
and I'm not that good in English though
Posted
Updated 5-Aug-21 22:22pm
v2
Comments
Richard MacCutchan 1-Aug-21 7:08am
   
The logic will be to capture all the values as described above, and applying a formula to get the optimum set of employees.

You don't seem to understand what this test is all about. It's not necessarily that you got a working app. What's being tested is your skills and process for getting to the answer you did.
   
You need to analyze every sentence and its content very carefully to understand the task and so find a solution.

"You want to hire some employees."
Your main task => the result should be a solution "I will hire that team or no one"

"There are N employees in total and each has skill U and wants salary V."
This is your starting point. N employes with a skill and salary.
Code may
C++
class Employee {
  string name; // or some identifier
  int skill; // or maybe an enum
  int salary; // salary
};
These employees are in a group which you can use an vector. And these groups you must rate via adding salaries and skills.
   
While we are more than willing to help those that are stuck, that doesn't mean that we are here to do it all for you! We can't do all the work, you are either getting paid for this, or it's part of your grades and it wouldn't be at all fair for us to do it all for you. And interviews count as homework: nobody wants to do it for you and then find themselves lumbered with a co-worker that can't do the job as a result!

So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!
Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.

If you are having problems getting started at all, then this may help: How to Write Code to Solve a Problem, A Beginner's Guide[^]
   
Comments
vfxguy.net 1-Aug-21 7:10am
   
I'm not asking for a direct solution,
can you explain to me the logic, I'm not able to understand the question something like in layman's terms.
and I'm not that good in English though
OriginalGriff 1-Aug-21 7:30am
   
Part of the test / assignment / homework is finding out how you take a specification (the text above), analyse it, and design a solution from that: if we do that part for you because you can't then that's unfair on those we don't help - and potentially gets you into an interview or job that you can't handle but that someone else could.

Think about it: you've got sample input, examples, and description: you should be able to work it out from that!
This is a straight forward question from graphs. you have to connect the edges on the basis of x and y (undirected) and then do a traversal on the graph until each node is visited. for each component you sum up the salary and skill number and if the final total salary of the component is less than the budget you can hire that group. Take an additional variable to store the max skill number among all the eligible groups.
   
v2

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900