TopCoder problem "ImportantTasks" used in SRM 447 (Division II Level One)



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.
 

Definition

    
Class:ImportantTasks
Method:maximalCost
Parameters:int[], int[]
Returns:int
Method signature:int maximalCost(int[] complexity, int[] computers)
(be sure your method is public)
    
 

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)
    
{100}
{100,100}
Returns: 1

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10578

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13901&pm=10578

Writer:

Gluk

Testers:

PabloGilberto , ivan_metelsky , ged

Problem categories:

Greedy