Greedy algorithm to maximize score

Question

I am trying to implement a method in java which takes as input an ArrayList of objects that have a deadline, a score, and object number. Each is accessible as:

game.get(i).number
game.get(i).score
game.get(i).deadline

Where game is the ArrayList and i is the index.

I want to maximize the score I can achieve while considering the deadline for each game. Each game has to be completed before the deadline. e.g. if deadline is 5, it has to be completed at 4 or earlier.

For example, here is a sample ArrayList with it's corresponding data organized in descending order of the score worth:

Index     Game number     Score     Deadline
0         3               76        3
1         4               66        2
2         1               52        2
3         6               51        4
4         5               47        2
5         2               23        1

Then the following ArrayList could be the result:

maximizedScore = [4,1,3,6] -> here each index represents the hour. Even though game 3 has a higher score than game 4 and game 1, we put game 4 in index 0 and game 1 in index 1 as they both have a deadline of 2 so they must be completed before then. However, game 3 has a deadline of 3 so we can do it at hour 2 in order to maximize the total score. Note that game 5 also has the same deadline as game 4 and 1, but it has less points than both so we sacrifice it.

Edit: Each index (0,1,2,3,4,..) represents the hour while the value at the index represents the game number being completed at that hour.

Edit 2: We can only do one game per hour. So if the latest deadline in the data is x, then we can do a max of x games. I.e. 4 in this example.

This provides a maximum score of 245.

The order of games does not matter as long as they are before the deadlines. For example: [1,4,3,6] would also be acceptable as both game 4 and game 1 are being completed before the deadline.

Unfortunately, I have no idea how to go about implementing this. Hopefully I provided a clear idea of what I need.

Any help is appreciated!

Answer 1

I will try to give a general approach without writing any code yet.

I will call the result you are looking for the "schedule". As you explained in your question, the maximum number of games you can place in your schedule is indicated by the maximum value in the "Deadline" column of your input data. I will call this the "time limit".

You are asking for a greedy algorithm. Such an algorithm will generate and check all game schedules to find the one that maximizes your score.

Basic approach

The most basic approach you can take is to generate all permutations of games of length "time limit" or less. For each one of them, you would then check:

• is it indeed a valid schedule (is each game in the tentative schedule payable at the time it is placed?),
• does this tentative schedule yield a total score greater than the best score obtained so far ? If so, you "keep" this solution and continue trying other schedules

The main difficulty in this first approach is to correctly generate all the possible schedules. I.E:

• 0
• 0 1
• 0 1 2
• 0 1 2 3
• 0 1 2 3 4
• 0 1 2 4
• 0 1 2 4 3
• 0 1 3
• ....
• 1
• 1 0
• 1 0 2
• ....

Optimizations

Now, the basic approach above has some ineficiencies. For instance, when you are building the possible schedule and you build one that is impossible due to the deadline criteria. For example:

• 3 5

is an impossible schedule because game "5" has a deadline of 1 (meaning it can only be played as the first game or not a all). If you can recognize this, then you realize that any schedule that starts with 3 5 (3 5 0 ..., 3 5 1 ...) is also impossible.

You can exploit this fact if you generate the schedule in a clever order and skip the generation of the schedules that you know are not going to be possible.

Tips for algorithm

I would suggest generating the schedules in a recursive manner. You have all your game ids (0, 1, etc) in a collection. You start with the lowest index: 0 , remove it from the collection of games and place it in your tentative schedule:

Schedule: 0

You check if it is a valid schedule (i.e. if the game you just placed in your schedule can be played at that time). Let's assume that it is the case (in this specific case as it is the first game on the schedule, it should always be possible). You also check if this tentative schedule yields a better score than anything you found so far.

Then you try to add the lowest game left in your collection of games left to play. In this case, 1. Same thing you remove 1 from the collection of games and place it on your schedule:

Schedule: 0 1

Same thing, you check if this is a valid schedule. You already know that game 0 can be played first, you check if game 1 can be played in second position. Bad luck, the time limit of game 1 prevents you from doing it. It is not worth exploring the schedules that start with 0 1 anymore. You remove 1 from your schedule, but you do not replace it in the games collection: as it is impossible to play in second position, it is not worth checking it further. Instead, I would place it in a collection of games that were "excluded" at the current exploration level.

You then move on to the next game remaining in the game collection, 2 and follow the same routine. If you are able to place a game on your schedule that is compatible with the time limit, you can continue adding games on you schedule with the ones that remain in the games collection. Be careful to recognize that there may be cases where you completely fill your schedule but there are still games left (or vice versa, you still have holes in your schedule but there are no games that can be played left).

When you have run out of options, it is time to remove games from the schedule. Remove the last game you placed on your schedule and place it back in the games collection. Also place the games that you have excluded at the current level back into the games collections. You can continue the schedule generation. Be careful not to take the game you just removed at this level again though.

Answer 2

First thing to do would be to sort your games by their score, because we want a game with a highest score first:

if you have an ArrayList of object say ArrayList<Game> inputData = new ArrayList<>(); you can sort it like this in java:

inputData.sort(Comparator.comparing(Game::getScore));

now the lowest score is first and the highest one is last.

Since we have to keep track of deadlines I would put them into a separate ArrayList and remove them one by one if needed:

ArrayList<Integer> deadlines = new ArrayList<>();
for(Game game : inputData) {
    if (!deadlines.contains(game.deadline))
        deadlines.add(game.deadline);
}

After that the idea is to iterate through inputData one by one and keep track of previousDeadline and currentDeadline. If we that the currentDeadline is greather than previousDeadline then that means that we can't accept any deadline that is before that. This can be done by checking deadlines list that we created earlier and removing deadlines from it.

int previousDeadline = -1; // initial value because there is no -1 deadline
for(int i = inputData.size()-1; i >= 0; i--) {
    int currentDeadline = inputData.get(i).deadline;
    
    // compare previous and currentDeadline and remove from deadlines list
    if(previousDeadline != -1 && previousDeadline < currentDeadline) {
        for(int j = 1; j < currentDeadline; j++) {
            deadlines.remove(Integer.valueOf(j));
        }
    }

    // add to result only if present in deadlines list and update previous deadline
    if (deadlines.contains(currentDeadline) ) {
        result.add(inputData.get(i).number);
        previousDeadline = inputData.get(i).deadline;
    }
}

If you give it a input that you provided you will get a list with [3, 4, 1, 6]

Here is a pastebin with code