Activity Selection Problem

#1

Q) You are given n activities (from 0 to n-1) 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.

Input Format
The first line consists of an integer T, the number of test cases. For each test case, the first line consists of an integer N, the number of activities. Then the next N lines contain two integers m and n, the start and end time of each activity.

Constraints
1<=t<=50
1<=n<=10000
1<=A[i]<=100

Output Format
For each test case find the maximum number of activities that you can do.

Sample Input
1
3
10 20
12 15
20 30

Sample Output
2

Explanation
Person can only do 0th and 2nd activities.

Please provide the code, along with the explaination of code. I am not able to solve this problem.

Thank You

#2

Approach
you have to use greedy algorithm to solve this
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 the 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 finishing time
  2. Select the first activity from the sorted array and print it.
  3. Do the following for the remaining activities in the sorted array.
    …….a) If the start time of this activity is greater than or equal to the finish time of the previously selected activity then select this activity and print it.
    In the following C implementation, it is assumed that the activities are already sorted according to their finish time

Code