Activity Selection Problem

Posted in

Activity Selection Problem

Maaz Bin Asad
Last updated on June 9, 2022

    Problem

    Given pairs of integers denoting starting and ending time of each task. Find maximum number of tasks a person can do provided that he can only do one task at a time

    Sample Input

    (1, 2), (2, 2)

    Sample Output

    (1,2)
    (2,2)

    Approach

    The algorithm follows a greedy approach. We can sort the tasks based on the ending time. Starting from the first task, if the starting time of the next task is greater than the ending time of the current task, a person can do that task. The approach takes O(NlogN) time due to sorting.

    C++

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <unordered_set>
    usingnamespacestd;
    structPair
    {
     int start, finish;
    };
    voidsolve(vector<Pair> tasks) 
    {
     int k = 0;
     unordered_set<int> Set;
     Set.insert(0);
     sort(tasks.begin(), tasks.end(),
     [](autoconst &x, autoconst &y) {
     return x.finish < y.finish;
     });
     for (int i = 1; i < tasks.size(); i++)
     {
     if (tasks[i].start >= tasks[k].finish)
     {
     Set.insert(i);
     k = i; 
     }
     }
     for (int i: Set)
     {
     cout << "(" << tasks[i].start << ", " << tasks[i].finish
     << ")" << endl;
     }
    }
    intmain()
    {
     vector<Pair> tasks =
     {
     {1, 2}, {2, 2}
     };
     solve(tasks);
     return0;
    }

    Output

    (2, 2)
    (1, 2)

    Python

    defsolve(tasks):
     k = 0
     Set = set()
     Set.add(0)
     tasks.sort(key=lambda x: x[1])
     for i in range(1, len(tasks)):
     if tasks[i][0] >= tasks[k][1]:
     Set.add(i)
     k = i 
     return Set
    tasks = [(1, 2), (2, 2)]
    ans = solve(tasks)
    print([tasks[i] for i in ans])

    Output

    [(1, 2), (2, 2)]

    Java

    import java.util.*;
    import java.util.stream.Collectors;
    classPair
    {
     privateint start, finish;
     publicPair(int start, int finish)
     {
     this.start = start;
     this.finish = finish;
     }
     publicintgetFinish() {
     return finish;
     }
     publicintgetStart() {
     return start;
     }
     @Override
     public String toString() {
     return"(" + getStart() + ", " + getFinish() + ")";
     }
    }
    classMain
    {
     publicstatic List<Pair> solve(List<Pair> tasks)
     {
     int k = 0;
     Set<Integer> ans = new HashSet<>();
     ans.add(0);
     Collections.sort(tasks, Comparator.comparingInt(Pair::getFinish));
     for (int i = 1; i < tasks.size(); i++)
     {
     if (tasks.get(i).getStart() >= tasks.get(k).getFinish())
     {
     ans.add(i);
     k = i; 
     }
     }
     return ans.stream()
     .map(tasks::get)
     .collect(Collectors.toList());
     }
     publicstaticvoidmain(String[] args)
     {
     List<Pair> tasks = Arrays.asList(new Pair(1, 2), new Pair(2, 2));
     List<Pair> ans = solve(tasks);
     System.out.println(ans);
     }
    }

    Output

    [(1, 2), (2, 2)]

    People are also reading:

    Leave a Comment on this Post

    0 Comments