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 ;
}
}
}
}
---------------------------------------------------------------------------------
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
Post a Comment