ImportantTasks
SRM 447 · 2009-08-25 · by Gluk
SRM 447 · 2009-08-25 · by Gluk · Greedy
Problem Statement
Problem Statement
At Facebook, different tasks have to be executed simultaneously on a limited number of computers. You are given a set of incoming tasks. Each computer can execute at most one task, and each task must be fully executed on a single computer. You are given int[] s complexity and computers. Element i of complexity is the complexity of the i-th task. Element i of computers is the maximal complexity of a task that can be handled by the i-th computer. Return the maximal number of tasks that can be executed on the given computers.
Constraints
- complexity will contain between 1 and 50 elements, inclusive.
- Each element of complexity will be between 1 and 1,000,000, inclusive.
- computers will contain between 1 and 50 elements, inclusive.
- Each element of computers will be between 1 and 1,000,000, inclusive.
Examples
0)
{1,2,3}
{2,2,2}
Returns: 2
The last task can't be executed on any of the computers.
1)
{1,2,3}
{3}
Returns: 1
The computer can run any of the tasks, but there's only one computer, so only one task will be executed.
2)
{3,5,1,7}
{9,4,1,1,1}
Returns: 3
It's impossible to execute all 4 tasks. In order to handle 3 tasks, you can execute task 0 on computer 1, task 2 on computer 2 and task 3 on computer 0 (all indices are 0-based).
3)
{5,2,7,8,6,4,2,10,2,3}
{4,1,3,6,2,10,11,1,1,3,4,2}
Returns: 8
4)
{45,36,24,36,24,46,38,27,49,13,27,35,18,6,42,20,19}
{15,36,35,32,22,36,24,10,6,43,32,51,32}
Returns: 12
Submissions are judged against all 160 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ImportantTasks with a public method int maximalCost(vector<int> complexity, vector<int> computers) · 160 test cases · 2 s / 256 MB per case