This is something I've long desired as well. But a kernel scheduler only has to decide what task to run right now, not when in the future to run other tasks. So those schedulers may help you with part of the problem, but there is a lot more here than they solve. And they have a key bit of information you aren't keeping; namely if a task is blocked or not. (Actually, the kernel is going to track process states, I'm over simplifying here.) You're going to need to know what a task is blocking on so that the user can tell you if the task is unblocked.
If you want to be able to schedule out your day, you're going to have to include an estimate of the time remaining for a task.
You'll want to tie task dependencies into it as well. And that's not even getting into scheduling things with external events like 'order book' -> 'wait for it to arrive' -> 'read book' prior to ordering the book.
I think you're going to find that the problem gets deep quickly, and that having a well-thought-through and always with you UI is going to be critical.
I think you can improve this by looking at the problem as a directed graph of pairs of positions.
For this example I will use the line with values -9, -6, -1, 3, and 5.
Because it's too hard to draw a graph with just text, I'm going to represent the pairs as a table. We can think of the cells as representing the state where all containers between those two positions have been collected. Each cell has two values, one representing the cost to go left, the other representing the cost to go right (to the next container).
The values can simply be calculated as the distance between the two points multiplied by the number of barrels outside of those two points + 1. Cells where both numbers have the same sign represent cases when all barrels of the opposite sign have been collected. These are calculated using only the number of barrels in the direction away from zero.
In the table values of X mean that you can't go in that direction (all the barrels in that direction have been taken). The rows represent the current position of the collector and the columns represent the location of the next opposite barrel.
+------+------+------+------+------+
| -9 | -6 | -1 | 3 | 5 |
+---+------+------+------+------+------+
|-9 | | | | X, 24| X, 14|
+---+------+------+------+------+------+
|-6 | 3, X | | | 9, 27| 6, 22|
+---+------+------+------+------+------+
|-1 | |10, X | |20, 8 |15, 18|
+---+------+------+------+------+------+
| 3 |24, 4 |27, 6 |16, 8 | | X, 2 |
+---+------+------+------+------+------+
| 5 |14, X |22, X |18, X | | |
+---+------+------+------+------+------+
The rules for moving between squares can be somewhat confusing.
For negative numbered columns, the rules are as follows:
- Going right moves down one cell.
- Going left moves down one cell and then mirrors across the diagonal.
- If the right value is X, going left moves up to the diagonal (where the column and row are equal) and left by one.
For positive numbered columns, the rules are as follows:
- Going left moves up one cell.
- Going right moves up one cell and then mirrors across the diagonal.
- If the left value is X, going right moves down to the diagonal and right by one.
Now we can run Dijkstra's algorithm to calculate the best path, using these movement rules to traverse the graph. Our starting positions are (-1, 3) and (3, -1) with initial costs of 5 and 15, respectively. Once we've calculated values for the two end positions (left of (-9, -9) and right of (5, 5)) the smaller of the two is our answer.
The running time for each of the steps are:
- O(N log N) for initially sorting the input values along the line
- O(N^2) for calculating the table/graph
- O(N^2 log N) for running Dijkstra's on the graph (Note: there are at most two edges for any given vertex).
The first two steps are dominated by the last, so your overall runtime is O(N^2 log N) which should be a good enough runtime for the challenge.
Best Answer
That definition of "algorithm" is extremely narrow. It applies only to non-interactive deterministic digital small-step algorithms.
However, algorithms need not be digital (consisting of discrete steps and operating on discrete values). They can also be continuous (consisting of discrete steps and operating on continuous values) or analog (continuous progress and operating on continuous values). They can be non-deterministic (actually, it turns out that non-determinism is just a form of interactivity). They can be interactive (i.e. interacting with an environment). They can be parallel (i.e. wide-step).
For example, the simple "bucket-of-rain" algorithm. This is an interactive digital small-step algorithm:
This is a perfectly valid algorithm. It even has steps and operates on discrete values (which isn't even necessarily required for it to be considered an algorithm).
It is, however, interactive. It depends on some environment outside of the algorithm. Mathematically, in algorithm theory, this is modeled as an oracle.
So, to answer your question: yes, what you have there, is an interactive algorithm, and the reading is definitely a part of it.