Skip to content
This repository has been archived by the owner on May 12, 2021. It is now read-only.

topinambours/Rehearsal-Problem

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

15 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Rehearsal problem

L'équipe


Input of the problem

Each line is a player, each collumn is a piece The problem is to find a sequence of pieces such that the waiting time is minimal.

R =

Modeling the problem

To compute the waiting time, we must know when a player start and when a player leave.

P = The prefix sum matrix

S = The suffix sum matrix

By multiplying P and S we obtain a matrix containing the range of presence of each players. We have zero when the player is not yet arrived or if he had leave.

Compute the waiting matrix

We now need to know when a player is waiting. We then multiply the matrix containing presence range with the input data where we applyed -1 to each cells. By doing that, whe now have 0 when a player is playing, and -1 when he is doing something else, we then use this matrix as a mask for the previous computed one.

Using this formula :

With n the range of players and m the range of pieces.

M =

As result we get the waiting matrix.

To conclude, we minimize the WaitingTime to find a solution of the problem.

Preview

About

No description, website, or topics provided.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published