Activity Selection Problem

Problem

Given pairs of integers denoting starting and ending time of each task. Find the 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:

• Find dropping point of an egg
• Print all subarrays of an array having distinct elements
• Find all symmetric pairs in an array of pairs
• Sort elements by their frequency and index
• Hybrid QuickSort Algorithm
• Quicksort algorithm using Hoare’s partitioning scheme
• Find a Pair with the given sum in a BST
• Create a mirror of an m–ary Tree
• Dutch National Flag Problem
• Longest? ?Bitonic? ?Subarray? ?Problem?