Teaching Kids Programming – Greedy Algorithm to Complete Tasks

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a list of integers tasks and another list of integers people. The integer tasks[i] represents the amount of strength required to perform the ith task. people[i] represents the amount of strength the ith person has.

Return the number of tasks that can be finished if one person can perform at most one task.

Constraints
n ≤ 100,000 where n is the length of tasks
m ≤ 100,000 where m is the length of people
Example 1
Input
tasks = [3, 2, 9, 13]
people = [10, 5, 2, 1]
Output
3
Explanation
First person can perform task 9
Second person can perform task 3
Third person can perform task 2
Fourth person can’t perform any tasks

Greedy Algorithm of Job Scheduler

We want to assign the tasks to the people with smallest strength if he/she can do it. Thus, we can apply the greedy strategy – sort both tasks efforts and strengths in ascending order. Then, if the current smallest strength can finish current smallest task – good, we increment the answer (completed task by one) and move forward two pointers. Otherwise, we need to try next large strength.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def completeTasks(self, tasks, people):
        if not tasks or not people:
            return 0
        tasks.sort()
        people.sort()
        i, j = 0, 0
        t, p = len(tasks), len(people)
        ans = 0
        while i < t and j < p:
            if people[j] >= tasks[i]:
                ans += 1
                i += 1
            j += 1
        return ans

class Solution:
    def completeTasks(self, tasks, people):
        if not tasks or not people:
            return 0
        tasks.sort()
        people.sort()
        i, j = 0, 0
        t, p = len(tasks), len(people)
        ans = 0
        while i < t and j < p:
            if people[j] >= tasks[i]:
                ans += 1
                i += 1
            j += 1
        return ans

Sorting two arrays (of size N) takes O(NLogN) time – and the two pointer algorithm that implements greedy strategy takes O(N) time. Overall time complexity is O(NLogN). The Space complexity is O(1) constant.

–EOF (The Ultimate Computing & Technology Blog) —