ImportantTasks

SRM 447 · 2009-08-25 · by Gluk

SRM 447 · 2009-08-25 · by Gluk · Greedy

Show categories

Class Name: ImportantTasks

Return Type: int

Method Name: maximalCost

Arg Types: (vector<int>, vector<int>)

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.

Statement by TopCoder, Inc. — view the original on the archive.

Examples

{1,2,3}
{2,2,2}
Returns: 2

The last task can't be executed on any of the computers.

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

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

{5,2,7,8,6,4,2,10,2,3}
{4,1,3,6,2,10,11,1,1,3,4,2}
Returns: 8

{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