Return to Revisions

I actually thought of a possible solution that should be O(M log M), but it is after a little bit of thinking for the goal of optimization. I don't think the short 20 minutes in an interview really mean anything whether you think of it or not. Sometimes you also wanted to be more friendly and social when you talk during the interview, so the logical side of you might not be running at full speed.

Here is my solution:

1. Just break down the data point (123, 456.7, 10) into two items: (123, 10) and (456.7, -10) to signify the increase of workload, and the decrease of workload.

2. Now, you just keep a data structure of: at which time, the work load becomes what value. So for example, when you see (123, 10), then set or increase workload[123] by 10. (but how do you know what workload is at time 123 or right before time 123? See the description in step 6 later on).

3. So if the workload in step 2 exceed the maximum workload, you can already return false (and not add this "task", I suppose, because it exceeds the maximum workload -- meaning undo (2) or just do this test before doing step (2))

4. Likewise, set or decrease workload[456.7] by 10.

5. Maintain a binary tree of these time-points. So this tree will now have leaf node of 123 and 456.7. Note that when you search or insert to this binary tree, it is O(log M).

6. Now you can repeat step (1) for the next data point. But so note that in step (1), how do you find out whether it exceeds or not? It is by doing a binary search. For example, when the next data point is (234, 345, 20), then search for 234 in the binary tree for the equal or less leaf node. Now you will see the 123, and use the workload[123] to know of the existing workload, when it is reaching time 234.

Doing so, with M data point entering, the time to tell yes or no, should be O(M log M).