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

121 Solutions
41 Solvers

Last Solution submitted on Aug 07, 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 Solvers41

Problem Tags