Program for activity selection exceeds time limit

Question

I've been trying to solve this problem for some while and the solution I have come up with exceeds the lime limit by 1-3 ms and 2 out of 10 tests get a memory issue error. Why is that? This is the code for my solution:

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

using namespace std;

ifstream in("planificare.in");
ofstream out("planificare.out");

struct show {
    int start, finish, used = 0;
};

bool end_time (show lhs, show rhs) {
    if (lhs.finish == rhs.finish) return lhs.start < rhs.start;
    return lhs.finish < rhs.finish;
}

int main() {
    int participants, tv_chan;
    vector<show> prog;
    in >> participants >> tv_chan;
    for (int i = 1; i <= participants; i++) {
        show a;
        in >> a.start >> a.finish;
        prog.push_back(a);
    }
    sort(prog.begin(), prog.end(), end_time);
    int maxActivities = 0;
    int unused = 0;
    for (int i = 1; i <= tv_chan; i++) {
        while (prog[unused].used)
            unused++;
        int lastFinish = prog[unused].finish;
        prog[unused].used = 1;
        maxActivities ++;
        for (int j = 0; j < prog.size(); j++) {
            if (prog[j].start >= lastFinish && prog[j].used == 0) {
                maxActivities++;
                lastFinish = prog[j].finish;
                prog[j].used = 1;
            }
        }
    }
    out << maxActivities;
}

Planificare - InfoArena

Talent Day is coming soon at the Blomkvist TV channel and the CEO Mike needs you to make the program grid. \$N\$ participants have enrolled to expose their talents, each communicating the amount of time it needs. Mike's TV Chain consists of \$K\$ stations, (Blomkvist 1, Blomkvist 2, ... Blomkvist K) that transmit independently of each other. Due to the fact that all \$K\$ stations are all just as popular as the other, the participants are indifferent to which they will appear.

Knowing that at any given moment any station will broadcast a single show, determining the maximum number of shows that can be televised.

Input data

The input file planificare.in will contain on the first line \$2\$ natural numbers: \$N\$ and \$K\$. On each of the following \$N\$ lines there will be 2 values, the starting time and the end time, representing the time interval during which the participant performs its activity.

Output data

The output file planificare.out will contain the number requested by Mike on the first line.

Restrictions and clarifications

\$1 \le N \le 100,000\$

\$1 \le K \le 100,000\$

\$1 \le \text{start}_i \le \text{stop}_i \le 1,000,000,000\$

Time limit: 0.2 seconds

For 30% of the tests, \$N\$ ≤ 2000 and for another 10% of the tests, \$K\$ = 1. At each channel, a show can start at the same time that the previous one is over.

Example

planificare.in

2 1
1 4
4 8

planificare.out

2

Answer 1

The problem is that you are erasing elements from prog and then without bounds checking access it with prog[j]. That is sure to fall over.

Your end_time function is commonly known as operator< So you should use the appropriate name.

There is no comment on the significance of 1 and why a program should not be reordered when it starts at 1. It seems that different programs with starting time 1 should still have an ordering.

You are inconsistent in your loops. Once goes from 1 to <= participants the other goes from 0 to < participants. The latter is the commonly used one.

The first loop seems to sort for start time? You can achieve the same if you create a proper operator<.

using namespace std; is bad practice. There is no benefit to it other that you do not really know what is standard and what not, which is actually bad. Also it isprone to name clashes. Use what you need and not everything C++ has in the box

Answer 2

After consulting with a friend, I ended up with this code:

#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>

using namespace std;

ifstream in("planificare.in");
ofstream out("planificare.out");

int main() {
    int participants, tv_chan;
    vector<pair<int, int> > prog;
    in >> participants >> tv_chan;
    for (int i = 1; i <= participants; i++) {
        int s, f;
        in >> s >> f;
        prog.push_back(make_pair(f, s));
    }

    sort(prog.begin(), prog.end());

    int maxActivities = 0;
    multiset<int> actFinish;
    for (int i = 1; i <= tv_chan; i++) {
        actFinish.insert(0);
    }

    for (int i = 0; i < participants; i++) {

        multiset<int>::iterator it = actFinish.lower_bound(prog[i].second);
        if (it == actFinish.end()) it--;
        if (*it > prog[i].second && it != actFinish.begin()) it--;

        if (*it <= prog[i].second) {
            maxActivities++;
            actFinish.erase(it);
            actFinish.insert(prog[i].first);
        }
    }
    out << maxActivities;
}

Multiset is for storing more of the same elements, lower_bound returns the iterator to the first element in my multiset that is greater or equal than the specified begin_time.

The first if is to reduce the iterator, if it's more than the number of elements in my multiset and the second one is to reduce the iterator, if the number in the mutliset represented by it is greater than the specified begin_time.