Activity Selection Problem
The activity selection problem is an optimization problem used to find the maximum number of activities a person can perform if they can only work on one activity at a time.
Problem Statement: You are given n activities with their start and finish times. Select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time.
Approach:
The greedy choice is to always pick the next activity whose finish time is the least among the remaining activities and the start time is more than or equal to the finish time of the previously selected activity. We can sort the activities according to their finishing time so that we always consider the next activity as the minimum finishing time activity.
Here in this image we can see the selected activities.
Time Complexity: O(N * logN)
Auxiliary Space: O(1)
Greedy Algorithm Notes for GATE Exam [2024]Fractional Knapsack ProblemOptimal File Merge PatternsPrim’s Algorithm for Minimum Spanning Tree (MST)
In the dynamic landscape of algorithmic design, Greedy Algorithms stand out as powerful tools for solving optimization problems. Aspirants preparing for the GATE Exam 2024 are poised to encounter a range of questions that test their understanding of Greedy Algorithms. These notes aim to provide a concise and insightful overview, unraveling the principles and applications of Greedy Algorithms that are likely to be scrutinized in the upcoming GATE examination.
Table of Content
- Introduction to Greedy Algorithms:
- Activity Selection Problem:
- Job Sequencing Problem
- Huffman Coding
- Kruskal’s Minimum Spanning Tree Algorithm
- Dijkstra’s shortest path algorithm
- MCQ Questions for Greedy Algorithm