How to implement when given activities are not sorted?
We create a structure/class for activities. We sort all activities by finish time (Refer sort in C++ STL). Once we have the activities sorted, we apply the same algorithm.
Below image is an illustration of the above approach:
Below is the implementation of the above approach:
C++
// C++ program for activity selection problem // when input activities may not be sorted. #include <bits/stdc++.h> using namespace std; // A job has a start time, finish time and profit. struct Activitiy { int start, finish; }; // A utility function that is used for sorting // activities according to finish time bool activityCompare(Activitiy s1, Activitiy s2) { return (s1.finish < s2.finish); } // Returns count of the maximum set of activities that can // be done by a single person, one at a time. void printMaxActivities(Activitiy arr[], int n) { // Sort jobs according to finish time sort(arr, arr + n, activityCompare); cout << "Following activities are selected :\n"; // The first activity always gets selected int i = 0; cout << "(" << arr[i].start << ", " << arr[i].finish << ")"; // Consider rest of the activities for (int j = 1; j < n; j++) { // If this activity has start time greater than or // equal to the finish time of previously selected // activity, then select it if (arr[j].start >= arr[i].finish) { cout << ", (" << arr[j].start << ", " << arr[j].finish << ")"; i = j; } } } // Driver code int main() { Activitiy arr[] = { { 5, 9 }, { 1, 2 }, { 3, 4 }, { 0, 6 }, { 5, 7 }, { 8, 9 } }; int n = sizeof(arr) / sizeof(arr[0]); // Function call printMaxActivities(arr, n); return 0; } |
Java
// Java program for activity selection problem // when input activities may not be sorted. import java.io.*; import java.util.*; // A job has a start time, finish time and profit. class Activity { int start, finish; // Constructor public Activity(int start, int finish) { this.start = start; this.finish = finish; } } // class to define user defined comparator class Compare { // A utility function that is used for sorting // activities according to finish time static void compare(Activity arr[], int n) { Arrays.sort(arr, new Comparator<Activity>() { @Override public int compare(Activity s1, Activity s2) { return s1.finish - s2.finish; } }); } } // Driver class class GFG { // Returns count of the maximum set of activities that // can // be done by a single person, one at a time. static void printMaxActivities(Activity arr[], int n) { // Sort jobs according to finish time Compare obj = new Compare(); obj.compare(arr, n); System.out.println( "Following activities are selected :"); // The first activity always gets selected int i = 0; System.out.print("(" + arr[i].start + ", " + arr[i].finish + ")"); // Consider rest of the activities for (int j = 1; j < n; j++) { // If this activity has start time greater than // or equal to the finish time of previously // selected activity, then select it if (arr[j].start >= arr[i].finish) { System.out.print(", (" + arr[j].start + ", " + arr[j].finish + ")"); i = j; } } } // Driver code public static void main(String[] args) { int n = 6; Activity arr[] = new Activity[n]; arr[0] = new Activity(5, 9); arr[1] = new Activity(1, 2); arr[2] = new Activity(3, 4); arr[3] = new Activity(0, 6); arr[4] = new Activity(5, 7); arr[5] = new Activity(8, 9); // Function call printMaxActivities(arr, n); } } // This code is contributed by Dharanendra L V. |
Python3
''' Python program for activity selection problem when input activities may not be sorted.''' def MaxActivities(arr, n): selected = [] # Sort jobs according to finish time Activity.sort(key=lambda x: x[1]) # The first activity always gets selected i = 0 selected.append(arr[i]) for j in range(1, n): '''If this activity has start time greater than or equal to the finish time of previously selected activity, then select it''' if arr[j][0] >= arr[i][1]: selected.append(arr[j]) i = j return selected # Driver code if __name__ == '__main__': Activity = [[5, 9], [1, 2], [3, 4], [0, 6], [5, 7], [8, 9]] n = len(Activity) # Function call selected = MaxActivities(Activity, n) print("Following activities are selected :") print(selected[0], end = ""); for i in range (1, len(selected)): print(",", end = " ") print(selected[i], end = "") # This code is contributed by kshitijjainm |
C#
// C# program for activity selection problem // when input activities may not be sorted. using System; using System.Collections.Generic; using System.Linq; // A job has a start time, finish time and profit. class Activity { public int start, finish; // Constructor public Activity(int start, int finish) { this.start = start; this.finish = finish; } } // Driver class class GFG { // Returns count of the maximum set of activities that // can // be done by a single person, one at a time. static void printMaxActivities(List<Activity> arr, int n) { // Sort jobs according to finish time arr = arr.OrderBy(a => a.finish).ToList(); Console.WriteLine( "Following activities are selected :"); // The first activity always gets selected int i = 0; Console.Write("(" + arr[i].start + ", " + arr[i].finish + ")"); // Consider rest of the activities for (int j = 1; j < n; j++) { // If this activity has start time greater than // or equal to the finish time of previously // selected activity, then select it if (arr[j].start >= arr[i].finish) { Console.Write(", (" + arr[j].start + ", " + arr[j].finish + ")"); i = j; } } } // Driver code public static void Main(string[] args) { int n = 6; List<Activity> arr = new List<Activity>(); arr.Add(new Activity(5, 9)); arr.Add(new Activity(1, 2)); arr.Add(new Activity(3, 4)); arr.Add(new Activity(0, 6)); arr.Add(new Activity(5, 7)); arr.Add(new Activity(8, 9)); // Function call printMaxActivities(arr, n); } } // This code is contributed by phasing17 |
Javascript
<script> /* JavaScript program for activity selection problem when input activities may not be sorted.*/function MaxActivities(arr, n){ let selected = []; // Sort jobs according to finish time Activity = Activity.sort(function(a,b) { return a[1] - b[1]; }); // The first activity always gets selected let i = 0 selected.push(arr[i]); for(let j=1;j<n;j++){ /*If this activity has start time greater than or equal to the finish time of previously selected activity, then select it*/ if( arr[j][0] >= arr[i][1]){ selected.push(arr[j]); i = j; } } return selected; } // Driver code Activity = [[5, 9], [1, 2], [3, 4], [0, 6],[5, 7], [8, 9]]; n = Activity.length; selected = MaxActivities(Activity, n); document.write("Following activities are selected : <br>") console.log(selected) for(let i = 0;i<selected.length;i++) document.write("("+selected[i]+"), ") </script> |
Output
Following activities are selected : (1, 2), (3, 4), (5, 7), (8, 9)
Time Complexity: O(N log N), If input activities may not be sorted. It takes O(n) time when it is given that input activities are always sorted.
Auxiliary Space: O(1)
Activity Selection Problem | Greedy Algo-1
Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. Greedy algorithms are used for optimization problems.
An optimization problem can be solved using Greedy if the problem has the following property:
- At every step, we can make a choice that looks best at the moment, and we get the optimal solution to the complete problem.
If a Greedy Algorithm can solve a problem, then it generally becomes the best method to solve that problem as the Greedy algorithms are in general more efficient than other techniques like Dynamic Programming. But Greedy algorithms cannot always be applied. For example, the Fractional Knapsack problem can be solved using Greedy, but 0-1 Knapsack cannot be solved using Greedy.