Problem 45416. Don't be Greedy!

Created by Asif Newaz

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>A list of assignments is given to the students along with the submission deadlines. Each of the assignment contains particular marks.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>If the student can submit a particular assignment within its deadline, he'll get marks.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>But he can submit only one assignment per day.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>For instance,</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ Assignment = [ a1, a2, a3, a4, a5, a6]\n Marks      = [ 60,100, 20, 40, 20, 10]\n Deadline   = [  2,  1,  3,  2,  1,  3]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Now, on the 1st day - he can submit one among all the assignments. But in the 2nd day, he can no longer submit a2 &amp; a5.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>He wants to achieve maximum marks by carefully submitting those assignments within the deadlines. Can u help him?</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The answer should be - [a2,a1,a3]. Since by submitting in this sequence, he can get the maximum marks.</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

79 Solutions
5 Solvers

Last Solution submitted on Oct 14, 2020

Last 200 Solutions

Problem Comments

8 Comments

8 Comments

Show 5 older comments

Binbin Qi on 4 Apr 2020

I think the solution is not unique.

Asif Newaz on 4 Apr 2020

can u tell me where/which test suite u're facing problem?
cz I think the solution should be unique since there is only one parameter.

Binbin Qi on 5 Apr 2020

In the test2. Why [7 3 4 5 6] is not right?

Asif Newaz on 5 Apr 2020

ok..i see..
if there are more than one possibilities..they should be placed in sorted manner. that should do it

Binbin Qi on 5 Apr 2020

sorted?[3 4] or [4 3] in test2?

Asif Newaz on 6 Apr 2020

sorted based on the marks --
[40,50] == [4,3]

Nikolaos Nikolaou on 7 Apr 2020

found it difficult but fun :)

Rafael S.T. Vieira on 14 Oct 2020 at 22:51

The problem is not difficult, but the test suite should accept all possible solutions since there is not an unique order, for instance at test cases #2 and #4. Sorting values increases this problem's difficulty since there may be several works with the same (or complementary) weight that can be done to achieve the same score (a proper description should be added to the problem since there may cases which are not trivial to sort).

PS: In this problem when any two works have the same deadline, but their marks differ, the lowest mark should come first (which seems weird). And no explanation is given for two works that have the same deadline and mark (but at least there isn't a case at the test suite).

Problem Recent Solvers5

Problem Tags

algorithm

Community Treasure Hunt

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

Start Hunting!

Problem 45416. Don't be Greedy!

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers5

Suggested Problems

More from this Author149

Problem Tags

Community Treasure Hunt

Problem 45416. Don't be Greedy!

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers5

Suggested Problems

More from this Author149

Problem Tags

Community Treasure Hunt

Players