Activity Selection to maximize the number of activity executions

Question

I solved this problem from a challenge.The problem is as below:-

Problem Statement:

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 activities which can be performed in new line.

Constraints:

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

Example:

Input:

2
6
1 3 2 5 8 5
2 4 6 7 9 9
4
1 3 2 5
2 4 3 6

Output:

4
4

C++ code for the problem:-

#include<iostream>
void swap(int a[],int i,int j)
{
    int temp=a[i];
    a[i]=a[j];
    a[j]=temp;
}
int activitySelection(int start[], int end[], int n){

    long i,j,count=1,pointer;
    for(i=0;i<n;i++)         //sorting both arrays in the order of the end array
    {
        for(j=i+1;j<n;j++)
        if(end[j]<end[i])
        {
            swap(end,i,j);
            swap(start,i,j);
        }

    }
    pointer=end[0];  //pointer set to end time of the first activity 
    for(i=1;i<n;i++)
    {
        if(start[i]>=pointer) //if 
        {
            count++;

            pointer=end[i];
        }

    }
    return count;
}
int main()
{
  int t;
  std::cin>>t; /*number of testcases*/
  while(t--)
  {
    int n;
    std::cin >> n;
    int start[n], end[n];
    for(int i=0;i<n;i++)
        std::cin>>start[i];
    for(int i=0;i<n;i++)
        std::cin>>end[i];

   std:: cout << activitySelection(start, end, n) << std::endl;
  }
}

The code works as I intended to.But there are few openings that i feel could be improved in the code.The above code basically sorts the both arrays according to the end[] array.Then it checks if the starting time of the current activity is greater or equal to the end time of the previous activity,if yes then count increments and the pointer is set to the end time of the current activity for comparing the next activity.Two things i want to know:

1.Is there a better approach than sorting arrays and comparing?

2.What is a better way to sort the two arrays on the basis of the second array?

Please suggest changes to improve.Thanks for reading ;-)

Answer 1

Note: your code doesn't currently compile for at least two reasons: you are not telling the compiler cout and endl live in the std namespace, and you can't declare your arrays start and end because n is not known at compile-time (instead, you'd have to use dynamic memory allocations).

In any case, your code smells like your background might be in C (but then you'd probably also know about dynamic memory... well, anyway). Indeed, with C++, you typically define variables as close to their site of usage. Moreover, you could take advantage of the algorithms and data structures provided by the language.

1. Is there a better approach than sorting arrays and comparing?

Essentially no: you must sort the arrays (with no additional knowledge, you can't beat the log-linear bound). This dominates your runtime, but it is scalable and practical enough that you don't have to worry about it.

2. What is a better way to sort the two arrays on the basis of the second array?

Because start and end times are logically and tightly coupled (i.e., something is wrong if we suddenly lose the correspondence), it's a good idea to tie them together. For that reason, we can use std::pair. To store such objects, we can use a dynamic array, i.e., std::vector. For sorting that according to the second element, we can use std::sort.

To summarize, we could proceed along the following lines (I'm taking the liberty to omit reading input to avoid clutter):

#include <iostream>
#include <algorithm>
#include <vector>

typedef std::vector<std::pair<int, int> > PairList;

int activitySelection(const PairList& p) 
{
    PairList s(p);
    std::sort(s.begin(), s.end(), [](const auto& x, const auto& y) {
        return x.second < y.second;
    });

    int end = s[0].second;
    int count = 1;

    for (int i = 1; i < s.size(); ++i)
    {
        if (s[i].first >= end)
        {
            ++count;
            end = s[i].second;
        }
    }

    return count;
}

int main()
{
    PairList v{ {1,2},{3,4},{2,6},{5,7},{8,9},{5,9} };
    std::cout << activitySelection(v) << "\n";
}