ACTIVITY SELECTION PROBLEM

Last Updated on March 28, 2022 by Ria Pathak

CONCEPTS USED:

Greedy algorithm.

DIFFICULTY LEVEL:

Medium.

PROBLEM STATEMENT(SIMPLIFIED):

PrepBuddy is given N activities with their start and finish times. The task is to select the maximum number of activities that can be performed by PrepBuddy, assuming that he can only work on a single activity at a time.

See original problem statement here

For Example :

2
5
1 3 4 6 8
3 5 13 14 15
6
3 5 6 7 8 9
5 7 8 9 10 12

3
4

In the first test case, the activities present at index 0, 1 and 3 can be completed.
In the second test case, the activities present at index 0, 1, 3 and 4 can be completed.

OBSERVATION:

Activity selection problem is one of the most frequently asked problems and also holds great significance when it comes to implementing greedy algorithm.

The activity selection problem is a combinatorial optimization problem concerning the selection of non-conflicting activities to perform within a given time frame, given a set of activities each marked by a start time (si) and finish time (fi). The problem is to select the maximum number of activities that can be performed by a single person or machine, assuming that a person can only work on a single activity at a time. The activity selection problem is also known as the Interval scheduling maximization problem (ISMP), which is a special type of the more general Interval Scheduling problem.

SOLVING APPROACH:

What does greedy say???

It says that, at every step, we can make a choice that looks best at the moment, and we get the optimal solution of the complete problem.

Here,the greedy choice is to always pick the next activity whose finish time is least among the remaining activities and the start time is more than or equal to the finish time of previously selected activity.

We can sort the activities according to their finishing time so that we always consider the next activity as minimum finishing time activity.

1. Sort the activities according to their finish time.

2. Select the first activity and set the counter to 1.

3. Now iterate over the entire array and keep comparing the selected finish time with the current start time.

4. If the start time is greater ,increment the counter by 1 and change the value of the selected finish time to the current finish time.

Time Complexity:
When activities are sorted by their finish time: O(N)
When activities are not sorted by their finish time, the time complexity is O(N log N) due to complexity of sorting.

SOLUTIONS:

#include <bits/stdc++.h>
    using namespace std;

    int main()
    {
    int t;cin>>t;
    while(t--)
    {
    int n;cin>>n;
    vector<pair<int,int>>v(n);
    for(int i=0;i<n;i++)
    {
      int st;
      cin>>st;
      v[i].second=st;
    }
    for(int i=0;i<n;i++)
    {
      int end;
      cin>>end;
      v[i].first=end;
    }
    sort(v.begin(),v.end());
    int ans=1;
    int st=v[0].first;
    for(int i=1;i<n;i++)
    {
      if(v[i].second>=st)
      {ans++;
        st=v[i].first;
      }
    }
    cout<<ans<<"\n";
     }
     return 0;
    }

import java.util.*; 
   import java.lang.*; 
    import java.io.*; 

     class ActivitySelection 
    {
    public static void printMaxActivities(int s[], int f[], int n) 
    { 
    int i, j; 
       int count=1;
    i = 0; 
    for (j = 1; j < n; j++) 
    { 
         if (s[j] >= f[i]) 
         { 
              count=count+1; 
              i = j; 
          } 
     } System.out.println(count);
    } 
    public static void main(String[] args) 
    { 
    Scanner sc = new Scanner(System.in);
        int t= sc.nextInt();
        while(t-- >0 ){
            int n = sc.nextInt();
            int f[]=new int[n];
            int s[]=new int[n];
            for(int i=0;i<n;i++)
            {
              s[i] = sc.nextInt();
            }
            for(int i=0;i<n;i++)
            {
                f[i] = sc.nextInt();
            }

    printMaxActivities(s, f, n); }
    } 

     } 

#include <stdio.h>

int cmpfunc (const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}
int main(void) {
	// your code goes here
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		int start[n];
		int end[n];
		
		for(int i=0;i<n;i++)
		{
			scanf("%d",&end[i]);
		}
		for(int i=0;i<n;i++)
			scanf("%d",&start[i]);
		
		qsort(start, n, sizeof(int), cmpfunc);
		qsort(end, n, sizeof(int), cmpfunc);
		int ans = 1;
		int st = start[0];
		for(int i=1;i<n;i++)
		{
			if(end[i] >= st)
			{
				ans++;
				st = start[i];
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

# your code goes here
for _ in range(int(input())):
	
	n = int(input())
	v = []
	a1 = list(map(int,input().split()))
	a2 = list(map(int,input().split()))
	
	for i in range(n):
		v.append([a2[i], a1[i]])
	
	v.sort()
	ans = 1
	st = v[0][0]
	
	for i in range(1, n):
	
		if v[i][1] >= st:	
			ans += 1
			st = v[i][0]

	print(ans)

This article tried to discuss the concept of Greedy Algorithm. Hope this blog helps you understand and solve the problem. To practice more problems on Greedy Algorithm you can check out MYCODE | Competitive Programming.