2

I have a list of lists in the form l = [[1,2,3],[3,4,6],...]. There are m sublists each representing a player. Each player can perform a number of tasks (there are n tasks). I would like to find the shortest path through all the steps by minimizing the number of switches between players. So basically have the same player perform the tasks consecutively as often as possible. I'm trying to write an algorithm to optimize this that runs in polynomial time but I'm having a bit of trouble coming up with a good scheme. I was thinking it could be like Dijkstra's algorithm, but I'm not exactly sure how to adapt it to fit my case. Below a concrete example of what I want.

Example

n = 5 and m = 3 such that we have a list of lists l = [[1,2,5],[1,3,5],[2,3,4]]

The algorithm would return [0,2,2,2,0]

i.e. player 0 would be chosen first then swap to player 2 for 3 tasks than back to player 0 for the last task.

I'm just looking for pseudo code or a push in the right direction. Really struggling and brute force won't work for large numbers!

Improve this question
4
  • I'm voting to close this question as off-topic because seems like a better fit for cs.stackexchange.com Commented Sep 27, 2017 at 2:22
  • Where do you get this problem? any constraints i.e: maximum value of n, m, l ? Commented Sep 27, 2017 at 2:34
  • @PhamTrung this is an abstraction of a coding problem I have. No maximums, they can get quite big. Commented Sep 27, 2017 at 2:51
  • Can you share your brute force approach here? Commented Sep 27, 2017 at 2:57

1 Answer 1

Reset to default
3

Since it is never beneficial to have a player perform fewer consecutive tasks than he can, a simple greedy algorithm suffices to find the optimal solution:

  1. Starting with task 1, find the player that can execute the largest number of consecutive tasks starting with that first task.

  2. Starting with the first task that the previously found player can't do, find the player that can execute the largest number of consecutive tasks starting with that task.

  3. Repeat until all the tasks are done.

Here's a proof that this algorithm is optimal:

Let say there's an optimal solution that has player A performing tasks i through j and then player B performing tasks j+1 through k.

If there is any player (including A) that can perform tasks i through j+1, then we can use that player to do those tasks instead, and the solution will be as good or better. Either B will perform tasks j+2 through k, and the number of player switches will be the same, or j+1 = k and we won't need player B at all.

Therefore there is an optimal solution in which every chosen player maximizes the number of consecutive moves that can be performed by that player. In fact, since every such solution is equivalent, they are all optimal.

EDIT: As I was writing this, Pham suggests to use a segment tree, but no such complex data structure is necessary. If the sublists are sorted and you make an index from each task number to the sublist positions at which it can be found, then you can do this in O(N) time.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

This would take O(n*m) time, which is optimal.
Ha, yes. I meant to say O(N) time, i.e., linear in the size of the input, which is O(n*m) using the OP's original variables
On second thought, we should be able to do better than linear by using binary search on the sublists to find the contiguous streaks (assuming they're sorted as in the example). The time of this depends on the number and length of streaks, O(n log m) in the best case.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.