6
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Thanks! This was helpful! However, I use namespace std for conveniency, as I don't need to remove it in this current program - no functions created by me interfere with std ones. Inconsistency in the loops comes from the fact that I was taught to go from 1 to <= limit and that's what I've used for 3-4 years since I'm into programming and changing that habit can be hard and useless, if the loop I'm used to works fine. When it doesn't, I know I can go from 0 to < limit. One question remains unanswered, however. Why the time limit exceeded error ? \$\endgroup\$ – antoniu200 Jun 5 at 19:06
  • \$\begingroup\$ Also, the first loop takes the activities that start at moment 1 and puts them in the first positions. \$\endgroup\$ – antoniu200 Jun 5 at 19:07
  • \$\begingroup\$ And I used the bool end_time function for conveniece, again, as I don't need to overload an operator necesarily. \$\endgroup\$ – antoniu200 Jun 5 at 19:30
  • 1
    \$\begingroup\$ @antoniu200 Unfortunately you are factually wrong. First, there is no operator< defined. Until spaceship comes you have to write them manually. Second, you are sorting the array twice with respect to different proerties of your struct. You can sort it just once by using a better comparison function. Third there is no convinience won using end_time. operator< is not really longer and you wouldnt have to pass it to std::sort. Finally, using namespace std; is always bad. For such a tiny example fine, but in bigger project it will bite you. Why learn bad stuff? \$\endgroup\$ – miscco Jun 6 at 7:35
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.