#C10038. Maximum Task Completion

    ID: 39199 Type: Default 1000ms 256MiB

Maximum Task Completion

Maximum Task Completion

You are given two lists: one representing the durations of tasks and the other representing the maximum time each worker can invest. Each worker can only complete a task if the task's duration does not exceed the worker's capacity. A worker can complete at most one task. Your goal is to assign tasks to workers in such a way that maximizes the number of tasks completed.

The underlying idea is to use a greedy algorithm: sort both the tasks and workers in non-decreasing order. Then, iterate over workers and, for each worker, try to assign the smallest remaining task that they can complete. This guarantees the maximum number of tasks is achieved.

The relationship can be mathematically represented as follows: [ \text{If } w_i \geq t_j \text{ then worker } i \text{ can complete task } j. ]

inputFormat

The first line contains two integers (n) and (m), representing the number of tasks and the number of workers, respectively.\nThe second line contains (n) integers, where the (i)-th integer denotes the duration of the (i)-th task.\nThe third line contains (m) integers, where the (j)-th integer represents the maximum duration the (j)-th worker can handle.

outputFormat

Output a single integer, the maximum number of tasks that can be completed.## sample

3 3
2 3 5
4 1 3
2