You start by setting each element of libraries to zero. Then, for each program, you set the libraries used by the program to one. At the end, you count up the number of libraries whose entries are one. That is your return value.
Thinking about running times -- There will be at most 1,000 libraries for each program, and there are at most 100 programs. That means that you will set at most 1000*100 = 100,000 library entries to one. That is well within Topcoder's time limits (you get roughly 5,000,000 operations), so it is fast enough. And you'll note, it is not a complicated solution.
I include it below:
#include <string>
#include <vector>
#include <list>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
class SuperUserDo {
public:
int install(vector <int> A, vector <int> B);
};
int SuperUserDo::install(vector <int> A, vector <int> B)
{
int i, j;
vector <int> Libraries; /* This will contain 0 if a library is not
in use, and one if a library is in use. */
int total;
/* Initialize variables. Set the total to zero, and
set every element of the Libraries vector to zero. */
total = 0;
Libraries.resize(1001, 0);
/* For each program, set the libraries that the program uses to one. */
for (i = 0; i < A.size(); i++) {
for (j = A[i]; j <= B[i]; j++) Libraries[j] = 1;
}
/* Total up the libraries that are used, and return that value. */
for (i = 0; i < Libraries.size(); i++) total += Libraries[i];
return total;
}
|