Problem 42875. Assignment Problem

Created by Jerivington

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Given a matrix where row i corresponds to person i, and column j corresponds to task j and cell (i,j) corresponds to the time taken for person i to complete task j. Output an assignment array for the minimal time taken for all tasks.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>For example, if presented with the following matrix:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ x = [1,3,4,7;  \n      2,3,1,3;\n      4,2,3,7;\n      6,4,2,2;]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Your output array would be:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ a = [1,3,2,4].]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Where person one is assigned to task one, person three is assigned to task two , person two is assigned to task three and person four is assigned to task four.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This gives us a total time of 1+1+2+2=6 which is minimal.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

124 Solutions
33 Solvers

Last Solution submitted on Nov 27, 2020

Last 200 Solutions

Problem Comments

6 Comments

6 Comments

Show 3 older comments

Jan Orwat on 3 Jun 2016

In test #1 answer could be [1 4 2 3], couldn't it? It gives tt = 10, same as proposed [1 2 4 3].

James on 3 Jun 2016

You're correct, Jan. Both options give you a minimum time of 10.

goc3 on 23 May 2018

Additional test cases have been added.

Yuichi Tadokoro on 27 Jul 2018

I think that ones(4) in Test #3 should be eye(4), instead. Also, #1 has to be fixed as Jan pointed out.

goc3 on 30 Jul 2018

The corrections mentioned by Yuichi (and Jan) have been made.

Jean-Marie Sainthillier on 29 Nov 2019

Good problem.
How to proceed with larger matrix (where permutations are too expensive) ?

Solution Comments

Solution 901588

1 Comment

1 Comment

James on 3 Jun 2016

Should not need the '=' in the 'if j<=t' statement to get the "correct" answer, but that makes the code match the solution in the test suite.

Problem Recent Solvers33

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!