Algorithm correctness for Bank Kattis problem

Question

This is the problem I am referring to. In quick summary:

Input: An integer time T; the time in minutes in which a bank closes and a set of pairs c and t that denotes the amount of cash (integer) this person carries and the time in minutes from now after which person leaves if not served. It takes one minute to serve a person and you must begin serving a person at time t at the latest.

Output: Maximum amount of money that can be collected within closing time.

My approach was this: place all the people in a map that maps money to time. I sort this map by money. I then make a queue-like structure where I take the person with the most money and place him/her as far back as possible. If the spot is occupied, then I move forward until I find a spot. If I can't then I just don't add the person.

Below is my helper function to determine whether or not I can insert a person.

// returns index where we can insert, otherwise -1
int canInsert(bool* queue, int timeToInsert) {
    if (!queue[timeToInsert]) {
        return timeToInsert;
    } else {
        int index = timeToInsert-1;
        while (index >= 0) {
            if (!queue[index]) {
                return index;
            } else {
                index--;
            }
        }
        return -1;
    }
}

Here is the main driver function:

// moneyToTime is a map that maps a person's money to the time value
int Bank(int T, map<int, int> moneyToTime) {
    int answer = 0;
    bool queue[47] = {0};
    for (map<int,int>::reverse_iterator i = moneyToTime.rbegin(); i != moneyToTime.rend(); i++) {
        if (T > 0) {
            // try to insert. If we can, then add to sum. Otherwise, don't.
            int potentialIndex = canInsert(queue, i->second);
            if (potentialIndex != -1) {
                queue[potentialIndex] = 1;
                answer += i->first;
                T--;
            }
        } else {
            break;
        }
    }
    return answer;
}

Logically, this makes sense to me and it is passing almost all the test cases. There are a couple that are failing; I can not see what they are. The test case errors are in fact indicating wrong answer, as opposed to bad runtime errors. Can someone help me see the fallacy in my approach?

Answer 1

You don't show how you build the moneyToTime but anyway it looks like map<int, int> is a wrong type for that. Imagine you have many people with the same amount of money and different timings. How would you represent then in your moneyToTime?

If my theory is correct, an example like this should break your solution:

3 3
2000 2
2000 1
500 2

Obviously the best sum is 4000 = 2000 + 2000. I suspect you get only 2500.