Activity Selection

PROBLEM :
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.

Note : The start time and end time of two activities may coincide.

Input:
The first line contains T denoting the number of testcases. Then follows description of testcases. First line is N number of activities then second line contains N numbers which are starting time of activies.Third line contains N finishing time of activities.

Output:
For each test case, output a single number denoting maximum activites which can be performed in new line.

Constraints:
1<=T<=50
1<=N<=1000
1<=A[i]<=100

Example:
Input:
1
6
1 3 0 5 8 5
2 4 6 7 9 9

Output:
4

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

#include<iostream>
using namespace std;
#define max 1000
int Activity_Selection(int [],int [],int ) ;
void SortActivity(int [],int [],int ) ;
int main()
{
int t,no,i ;
int arr1[max],arr2[max] ;
cin>>t ;
while(t--)
{
   cin>>no ;
   for(i=0;i<no;i++)
       cin>>arr1[i] ;
   for(i=0;i<no;i++)
       cin>>arr2[i];
     
   cout<<Activity_Selection(arr1,arr2,no)<<endl ;
}
return 0;
}

int Activity_Selection(int arr1[],int arr2[],int no)
{
    int count ;
    count=0 ;
   
    SortActivity(arr1,arr2,no) ;
   
    count++ ;
    int curr=arr2[0] ;
    for(int i=1;i<no;i++)
    {
        if(arr1[i]>=curr)
        {
            count++ ;
            curr=arr2[i] ;
        }
    }
    return count ;
}

void SortActivity(int arr1[],int arr2[],int no)
{
    int temp ;
    for(int i=0;i<no-1;i++)
    {
        for(int j=0;j<no-i-1;j++)
        {
            if(arr2[j]>arr2[j+1])
            {
                temp=arr2[j] ;
                arr2[j]=arr2[j+1] ;
                arr2[j+1]=temp ;
               
                temp=arr1[j] ;
                arr1[j]=arr1[j+1] ;
                arr1[j+1]=temp ;
            }
        }
    }
}

---------------------------------------------------------------------------------

Comments

Popular posts from this blog

Count ways to N'th Stair(Order does not matter)

Replace all ‘0’ with ‘5’ in an input Integer

Chocolate Distribution Problem

Remove characters from the first string which are present in the second string

Primality Test ( CodeChef Problem code: PRB01 )