Activity Selection Problem - Greedy Algorithm

 Click Me
What is Activity Selection Problem?
We are given 'n' activities with their start and finish times and we have to select the maximum number of activities that can be performed by a single person, assuming that the person can only work on a single activity at a time.
  
 Activity A1 A2 A3 A4 A5 A6
 Start Time 0 3 1 5 5 8
 End Time  6 4 2 8 7 9


How are we gonna solve this Activity Selection Problem?  [Time Complexity - O(nlogn)  Space Complexity - O(n)]
As we want to cover the maximum number of tasks, we should complete all those tasks first that finish first. So our focus is going to be on the end time of tasks. 
1. Sort the tasks by the end time
2. Always pick the first task and initialize a variable prevTaskTime = end time of the first task
3. For all other tasks:
        4. if the current task's end time is greater than previous tasks end time:
                    5. Pick this task to do and update variable prevTaskTime to end time of the current task


Code:

import java.util.*;

// the class task.
// It will contain the start and end time of the individual tasks.
class Task{
    int startTime;
    int endTime;
    
    // constructor
    Task(int s, int e){
        this.startTime = s;
        this.endTime = e;
    }
}

public class Main {
    // the list to contain all tasks
    ArrayList<Task> taskList;
    
    // constructor
    Main(){
        this.taskList = new ArrayList<>();    
    }
    
    // helper method to sort the tasks by their end time
    private void sortTasksByEndTime(){
        // we have to write the comparator to sort these Task by the end time
        // It will tell how to compare the Task objects
        Comparator<Task> comparator = new Comparator<Task>(){
            
            // overriding COMPARE method.
            @Override
            public int compare(Task t1, Task t2){
                return t1.endTime - t2.endTime;
            }
        };
        
        // finally sorting in non-decreasing order
        Collections.sort(this.taskList,comparator);
        
    }
    
    // method to perform activity selection on given tasks list.
    public void activitySelection(){
        // first sort all the tasks in the tasks List
        sortTasksByEndTime();
        // picking the first task
        System.out.println("Task with start time: " + this.taskList.get(0).startTime + " endTime: " + this.taskList.get(0).endTime);
        
        int previousActivityEndTime = this.taskList.get(0).endTime;
        // count maximum number of tasks that can be done
        int totalActivities = 1;
        
        // for all other tasks select whih task to select
        for(int i=1;i<this.taskList.size();i++){
            Task currentTask = this.taskList.get(i);
            if(currentTask.startTime > previousActivityEndTime){
                System.out.println("Task with start time: " + currentTask.startTime + " endTime: "+ currentTask.endTime);
                previousActivityEndTime = currentTask.endTime;
                totalActivities++;
            }
        }
        
        System.out.println("Maximum number of activities that can be scheduled: " + totalActivities);
    }
    
    public static void main(String[] args) throws Exception {
        Main activity = new Main();
        
        // tasks start time
        int[] startTime = {0,3,1,5,5,8};
        // tasks end time
        int[] endTime = {6,4,2,8,7,9};
        
        // adding tasks to taskList
        for(int i=0;i<startTime.length;i++){
            activity.taskList.add(new Task(startTime[i],endTime[i]));
        }
        
        activity.activitySelection();
        
    }
}


Output :

Task with start time: 1 endTime: 2
Task with start time: 3 endTime: 4
Task with start time: 5 endTime: 7
Task with start time: 8 endTime: 9
Maximum number of activities that can be scheduled: 4

Comments

Post a Comment

Popular posts from this blog

Binary Heap - Introduction

Image
#Image Credit - GeeksForGeeks Types of heap: Min Heap - every node is less than or equal to  its children(s) Max Heap - every node is more than or equal to its children(s) Operations on any heap : create insert extract/delete - we can extract/delete only the top node in any heap traverse delete entire heap get size of heap peek top of heap We should prefer implementing binary heap using arrays and not linked list, as during bottom to top heapify, in reaching the bottom rightmost node we take only 0(1) time in case of array but we take 0(n) time in case of linked list because first, we need to level order traverse the binary heap tree to get bottom-most rightmost element.  Heaps are used to efficiently implement:  Prim's Algorithm Heapsort Priority queue
Read more

Divide and Conquer - Introduction

Image
What is Divide and Conquer? Divide and Conquer is an algorithm paradigm in which we break down a given problem into smaller sub-problems of similar type until the sub-problems are small enough to be solved directly. The solution to these sub-problems are then combined to give a solution to the original problem.  Study the diagram below, it will then make more sense about what we do in Divide and Conquer : Where to Apply Divide and Conquer? The Divide and Conquer can be applied to all those problems that show Optimal Substructure property.  So, What is this Optimal Substructure property now? If we can break down a problem into similar sub-problems and the solution of these sub-problems can be used to create the solution of the whole problem, then that problem is said to have the Optimal Substructure property. For eg. : Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2),    In this example, we can see that if we want to find the Fibonacci number at the nth place, we can br...
Read more

Bubble Sort

Time complexity - O(n^2)  || Space Complexity - O(1) Bubble sort is an inplace sorting algorithm, that means we do not any extra space while bubble sorting public class Main {     public static void main(String[] args) throws Exception {         int[] arr={1,4,4,5,6,2,3,90,120,43,0};                  System.out.println("UnSorted Array :");         for(int i=0;i<arr.length;i++){             System.out.print(arr[i]+" ");         }         System.out.println();         // bubble sort         for(int i=0;i<arr.length-1;i++){ // iterates through first to last cell             for(int j=0;j<arr.length-1-i;j++){ // inner loop controls swapping and extent to which swapping is to be performed in array     ...
Read more