StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><em>My main problem is: how can I find jobs that previously were carried out? I use a data structure of support?</em><br> The trick is, you don't need to know what jobs are completed already. Because you can execute them in the order of increasing deadline.</p> <p>Let's say, some optimal solution (yielding maximum profit) requirers you to complete job <code>A</code> (deadline <code>10</code>) and then job <code>B</code> (deadline <code>3</code>). But in this case you can safely swap <code>A</code> and <code>B</code>. They both will still be completed in time and new arrangement will yield the same total profit.<br> End of proof.</p> <p><em>As you would have written the equation of recurrence?</em><br> You already have general idea, but you don't need a loop (<em>min for 1<=i<=n</em>).</p> <pre><code>max_profit(current_job, start_time) // skip this job result1 = max_profit(current_job + 1, start_time) // start doing this job now finish_time = start_time + T[current_job] if finish_time <= D[current_job] // only if we can finish it before deadline result2 = max_profit(current_job + 1, finish_time) + V[current_job]; end return max(result1, result2); end </code></pre> <p>Converting it to DP should be trivial.</p> <p>If you don't want <code>O(n*max_deadline)</code> complexity (e.g., when <code>d</code> and <code>t</code> values are big), you can resort to recursion with <a href="http://en.wikipedia.org/wiki/Memoization" rel="nofollow">memoization</a> and store results in a hash-table instead of two-dimensional array.</p> <p><strong>edit</strong><br> If all jobs must be performed, but not all will be paid for, the problem stays the same. Just push jobs you don't have time for (jobs you can't finish before deadline) to the end. That's all.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload