Greedy algorithm error using c++ sets

Question

I've created a greedy algorithm to solve a problem (homework assignment) and since I'm learning c++ I would like to achieve the same thing but using sets.

Basically we submit the homework to an online platform, this platform as some test cases that we don't know of, and we get a score based on that. If we pass all test cases we have 100%;

The problem is like this.

We have an actor that wants to schedule appointments with the fans that answered an online questionnaire about him. Now he wants to choose the fan's that maximizes the sum of points in the questionnaire and respecting the fan's availability. He can see only one fan a day.

We have an input like this:

6
1 1 5  
2 2 4
3 1 2
4 3 1
5 1 6
6 2 2

Where the first line is the number of fans and following, in each line, we have the fan id, the fan available days and the fan points achieved in the online questionnaire. I must print the ids of the fans that the actor will see and the sum of combined points of the fans. So for the above input I have the following output:

2
4
5
11

Note that if two fans have the same points, the fan prefered should be the one with the lower ID.

I've started by sorting the fans by the points of the questionnaire (decreasing order) and then by the lower id. When reading the input, I'm adding the number of days to a set. My idea was like this:

When iterating over the data, I check if the fan in study days available is in the set. If it is, add this fan and remove the days from the set. If the fan days is not in the set, then get the upper_bound and decrease the iterator to set the fan on the first day lower that the initial day. The algorithm stops wen the set is empty or I iterate all over the fans.

Here is my greedy function:

void greedy() {
    fan_id.insert(questionnaire_result[0][0]);
    days_available.erase(questionnaire_result[0][1]);
    total_questionaire_sum += questionnaire_result[0][2];

    int i;
    for (i = 1; i < number_of_fans; i++) {
        if (days_available.empty()) {
            break;
        } else if (days_available.count(questionnaire_result[i][1])) {
            fan_id.insert(questionnaire_result[i][0]);
            days_available.erase(questionnaire_result[i][1]);
            total_questionaire_sum += questionnaire_result[i][2];
        } else {
            it = days_available.upper_bound(questionnaire_result[i][1]);
            if (it == days_available.begin()) {
                if (*it < questionnaire_result[i][1]) {
                    fan_id.insert(questionnaire_result[i][0]);
                    days_available.erase(*it);
                    total_questionaire_sum += questionnaire_result[i][2];
                }
            } else if (it == days_available.end()) {
                it--;
                if (*it < questionnaire_result[i][1]) {
                    fan_id.insert(questionnaire_result[i][0]);
                    days_available.erase(*it);
                    total_questionaire_sum += questionnaire_result[i][2];
                }

            } else {
                it--;
                if (*it < questionnaire_result[i][1]) {
                    fan_id.insert(questionnaire_result[i][0]);
                    days_available.erase(*it);
                    total_questionaire_sum += questionnaire_result[i][2];
                }
            }
        }
    }
}

I believe my problem is in this line:

it = days_available.upper_bound(questionnaire_result[i][1]);

I've tested many possibilities and this is working in all my test cases. Unfortunately, we don't have the test cases of the platform.

Does someone see an situation that my code fails? With this I'm getting 90% of the score.

EDIT:

As Edward pointed me out, I've managed to solve the problem like this:

When reading the input added this line of code:

max_days = max_days | questionnaire_result[i][1];

And then did this:

for (int j = 1; j < max_days + 1; j++) {
            days_available.insert(j);
        }

Problem solved

Answer 1

This input file will cause the program to generate an incorrect result:

2
1 2 6
2 2 5

Both fans are available either day, so it's clear that both fans could be visited and the total output score should be 11. Your algorithm, however, only chooses the first one and outputs a score of 6.