# Does the workload problem belong to a class of computer science problem?

I went for an interview, and got a workload problem:

``````Problem: write a function to tell whether a series of workloads will exceed

Timeslot and workload: example [(2, 6, 3), (3, 8, 2), ... ]
The (2, 6, 3) is begin time, end time, and workload
And it means from time 2 to time 6, the workload is 3
You can treat the 2, 6 as the UNIX epoch time.
The time may not be integers, so instead of 2, it can be 2.2
The input can be in any time order. For example: [(20, 60, 3), (3, 8, 2)]

Output: a boolean indicating whether the series of workload can fit in without
``````

The short question is: does this workload problem belong to a class of algorithm, and that when the array is empty, but data keep on coming in for `M` times and we need to tell possible or not, for `M` times, is there a better solution than `O(M * M)`?

Details:

If I focused on how to determine whether the time ranges will overlap with each other, it turns out it is not an easy solution.

So I am not sure whether this is suitable as an interview question, as you may either know how to solve it or you don't. If you have seen it before, you will solve it like a breeze. If you haven't seen it before, I don't think 20 minutes may be enough time for you to get unstuck.

You may want to think about how you may solve it, if you want to have some fun.

The simple solution, which I could come up with, but after 15 minutes later, actually, can be: simply use a dictionary, and use the time boundary as the key, and if it is `(2, 6, 3)`, then just mark it as `dict = 3` and `dict = -3`.

Likewise, for `(3, 8, 2)`, then `dict = 2` and `dict = -2`

(and actually, if we treat the time endpoint as inclusive, then we won't have `dict = -2` but have `dict = -2`, treating it as dropping some workload at time `9` instead of at `8`)

And then, once you have the whole dictionary, now loop through each key in the dictionary, in sorted order, and keep a `CurrentWorkLoad` number as the work load. So when you see `dict` as `3`, add `3` to `CurrentWorkLoad`, and when you see `dict`, add the `2` to `CurrentWorkLoad`, and when you see `dict`, add the `-3` to `CurrentWorkLoad`.

So as soon as `CurrentWorkLoad` is greater than `MaxWorkLoad`, then you can return `false` right away. Otherwise, at the end of the loop, simply return `true`.

And what if there is `(2, 6, 3)` and `(6, 8, 1)`, meaning that the endpoint can "overlap" at the time `6`? So I came up with, either use an array to remember all the values when it collides at `6`, or, simply add up the values. So the first time you see `(2, 6, 3)`, then `dict is -3`, and when you see `(6, 8, 1)`, then `dict += 1` and becomes `-2`.

So if in JavaScript, it is like

``````dict[beginTime] ||= 0;    // if not defined, then set it to 0

dict[endTime] ||= 0;
``````

and the rest of the algorithm will stay the same.

So the time complexity for the array size `N` is `O(N log N)`, because we need to sort the keys.

The interviewer then asked me, what if this operation is repeated `M` times?

So for example, if the initial array is empty, but data keep on coming in, for `M` times, and `M` can be a million or ten million. Then what is the time complexity? I initially said then it is `O(M * M log M)`, but later on found out it could be `O(M * M)`, because we don't need to sort the keys every time. We can just "insert" the key in an already sorted list.

Is there a class of algorithm or problem solving that is related to this and have a solution better than `O(M * M)`?

• Possible duplicate of What is O(...) and how do I calculate it? Jan 19, 2017 at 22:34
• it is not a duplicate of that question. If you say it is a duplicate, you can say for any algorithm question, it always is a duplicate of that question Jan 19, 2017 at 23:07
• I think for a bounded set of times, that could be done in O(n), using a sparse array (no sorting). However you over looked “The time may not be integers, so instead of 2, it can be 2.2”. Jan 20, 2017 at 9:02

Asking "does the workload problem belong to a class of algorithms" makes not much sense - the problem itself is not an algorithm. However, I assume your real question is to which class of algorithms your proposed solution belongs.

I see this in the category of sweep line algorithms. Though yours is not really a geometric problem, the main idea is the same: take alle relevant points "where something changes" on the x-axis (here the time line), sort them in ascending order, and then process them from left to right. In this processing step, some kind of "state" is changed at each relevant point in time. In geometric problems, this kind of state is often a geometric set of points or something similar, in your case it is simply the total workload.

The only thing I would change in your algorithm is, I would not use a dictionary as container. A simple list of number pairs ("point in time", "workload change") will do it, ordered by their first value. That does not change much to your solution, especially not the running time, it just avoids problems with duplicate keys.

• Doesn't putting numbers in the correct order problem belong to the class of "sorting" algorithms? Jan 20, 2017 at 17:45
• @太極者無極而生: sure, but I don't think one would classify the algorithm as a whole as a sorting algorithm. Sorting is IMHO just one part of the algorithm. Jan 20, 2017 at 20:01
• maybe a more exact phrase is, does the workload problem belong to a certain class of computer science problem? Jan 21, 2017 at 7:08
• @太極者無極而生: "sweep line algorithms" belong to computational geometrie, which belongs to computer science. Jan 21, 2017 at 7:37
• hm... if you convert the (2, 6, 3) into (2, 3) and (6, -3), then it looks like so simple a problem. If the interviewer gave the input in such form, it is almost a no-brainer to solve it... so the tough part of the problem is just to convert the input into a different format? hm... i still don't like this question if it is an interview question Jan 21, 2017 at 11:45

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` 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). (the `wordload` is a dictionary / hash).

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 the increase in 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 search in the binary tree. 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` to know of the existing workload, when it is reaching time `234`.

Doing so, with `M` data points entering as a data stream, the time to tell yes or no, should be `O(M log M)`.

Not sure exactly what you mean about data coming in for `M` times. If we assume an endless stream of `N` timeslot/workload triplets. The best I come up with is also `O(N*N)`. My main difference is that I do not use a dictionary/hashtable.

Basic idea: Initially we have 0 timeslots and there is no violation of `MaxWorkLoad`. On each new timeslot, find all overlapping timeperiods, and check if the new addition causes a violation. Worst case this all the current entries overlap.

If we use a sorted structure, we can sort entries by primarily begin time, with end time secondary (and for microoptimisation largest workload as the third priority). Then when we add a new timeslot `(xBegin, xEnd, workload)` we can find the right bound (and also do the insertion) in `log N` time, by comparing the `xEnd` with `yBegin` for the already inserted `y`. Then we sum the workload left until the end (we have to). If the sum at any point is larger than `MaxWorkLoad` then return true otherwise return false. Worst case we have to sum over `N` elements each time, which we would have to anyway if we just looped through all.

If the granularity of the workload is fixed, for example integers, and `M` is max workload then this changes to `O(min(N*M, N*N))`, because during the sum at most `M` entries will be processed.

I don't think in general you can do better than `O(N*N)`. You must remember all `N` values received at any moment (unless they agree on start and end time), in order to determine any future violation.

The most related problem I can think of is the Lecture Hall Assignment problem (in the bottom) which is `O(N*N)`. To convert `(xBegin, xEnd, K)`, to lecture hall activities, make `K` copies of `(xBegin, xEnd)`. Going the other direction we can reduce the decision variant of the lecture hall assignment problem to your problem. For each activity make a timeslot with the workload set to `1`. The lecture hall decision problem is satisfiable with `P` halls, if your corresponding problem is satisfiable with `MaxWorkLoad = P`. If we believe the decision version of the lecture hall problem is also at least `O(N*N)`, then so is your problem.

• yes, the last part of my question... if (2000, 300000, 3) comes in, then it is one time. So if this kind of data comes in 1,000,000 times, then `M` is 1,000,000. Jan 20, 2017 at 2:02
• Are you sure you can find the overlapping efficiently? So if `(1, 10000000000, 88)` comes in, it may overlap with 20000 sets of earlier data Jan 20, 2017 at 2:03
• I made a minor edit to my search since it was broken. You can certainly find any overlapping efficiently. But you can not be sure how many overlaps. So regardless of how easy it is to find the overlapping timeslots, worst case it is all of them. Jan 20, 2017 at 12:49
• Unfortunately I don't have reputation to make comments on other answers. But unless I misunderstand: @Lucas idea of splitting the segments is interesting. However, worst case, you create two new segments, and have to update all those inside, which all current in worst case - and that is for each timeslot. Then that operation on `N` elements alone `N` times make it `O(N*N)`? @richard's solution would only work if you do not add more data again. Otherwise it becomes equivalent to mine and @ 太極者無極而生 ? Jan 20, 2017 at 12:57

# Yet another way to do it.

Since the examiner asked "what if this operation is repeated M times?" I would go with a database algorithm to keep the data and minimize the need of recalculation of the past every time a new observation came in.

My approach is that the workload is a line segment. When a new observation came, break the existing line segments on the database to match and increase the load only for the segments inside the new observation. I did this way mostly for fun. It is an interesting concept and will need a lot more test cases to see if my math has no side-effects.

If I not mistaken the performance will be something like O(log2 N) profile. Being N the size of the table. Which depends on the data. If there is a lot of overlap that may not grow with the number of observations. In a real world case we may even delete periods too old because this out-of-order behavior that is in the problem statement is probably in the recent data.

By the way, I code that in about 20 minutes. But I already did programs with line segment intersection on the database 12 year ago.

### The problem you presented:

``````Problem: write a function to tell whether a series of workloads will exceed

Timeslot and workload: example [(2, 6, 3), (3, 8, 2), ... ]
The (2, 6, 3) is begin time, end time, and workload
And it means from time 2 to time 6, the workload is 3
You can treat the 2, 6 as the UNIX epoch time.
The time may not be integers, so instead of 2, it can be 2.2
The input can be in any time order. For example: [(20, 60, 3), (3, 8, 2)]

Output: a boolean indicating whether the series of workload can fit in without
``````

### My code

``````drop schema if exists t1 cascade;
create schema t1;
set search_path='t1';
create table segment
(
start_dt bigint,
end_dt bigint,
);
create index segment_idx_start_dt on segment(start_dt);
create index segment_idx_end_dt on segment(end_dt);

create or replace function segment_add(bigint,bigint,bigint) returns void as \$\$
declare
xr1 record;
xr2 record;
xr3 record;
xs bigint;
begin
raise info 'segment_add(%,%,%)', \$1, \$2, \$3;
-- select all segments where the \$1 is in (one or zero)
select into xr1 * from segment where \$1 > start_dt and \$1 < end_dt;
if xr1 is not null then
-- Split the segment on point \$1
insert into segment values

raise info 'del % %', xr1.start_dt, xr1.end_dt;
delete from segment where start_dt = xr1.start_dt and end_dt=xr1.end_dt;

end if;

-- select all segments where the \$2 is in (one or zero)
select into xr2 * from segment where \$2 > start_dt and \$2 < end_dt;
if xr2 is not null then
-- split the segment on pont \$2
insert into segment values

raise info 'del % %', xr2.start_dt, xr2.end_dt;
delete from segment where start_dt = xr2.start_dt and end_dt=xr2.end_dt;

end if;

-- add segments that does not exist yet
xs = \$1;
for xr3 in
select * from segment where start_dt between \$1 and \$2 order by start_dt
loop
if xs < xr3.start_dt then
-- there is no segment before the space
raise info 'add % % % (2)', xs, xr3.start_dt, 0;
insert into segment values (xs,xr3.start_dt,0);
end if;
xs = xr3.end_dt;
end loop;

if xs < \$2 then
raise info 'add % % % (3)', xs, \$2, 0;
insert into segment values (xs,\$2,0);
end if;

-- now I must have all the fragment created.... I just need to update it
update
segment
set
where
start_dt >= \$1 and end_dt <= \$2
;

end
\$\$ language 'plpgsql';

-- the answer should have 0-1 1-4 4-10 12-13 13-14 14-15
select * from segment order by start_dt;
``````

If we also consider “The time may not be integers, so instead of 2, it can be 2.2”, then the best I could do is O(n log n), with this algorithm.

• Sort by start time
• foreach item in queue
• if not item.is_started
• mark item as started
• reinsert in queue, key on appropriate-time (end_time if is_started else start_time)
• else

This is algorithm to solve your problem.

• What are you using to sort in O(n log n)? How are you getting O(n log n) with iterating and insert in a sorted queue? Jan 20, 2017 at 15:06
• There are plenty of sorts that can work in O(n log n), then we iterate O(n), re-inserting record in to queue only doubles n. This gives n log n + 2n = O(n log n) Jan 20, 2017 at 15:48
• But you are not just inserting in the queue. You sorting on appropriate-time and that is not O(1). Jan 20, 2017 at 15:50
• Ah you are correct insertion in log n, that gives us n log n + 2n log n = O(n log n) Jan 20, 2017 at 16:24
• isn't this almost the same as my original algorithm? except you keep on reinserting and re-sorting Jan 21, 2017 at 7:06

O(n)

Pretty simple

• Create an array for load for each slot
For 3, 5, 7 just add 7 to 3, 4, and 5 slots

Does not require sorted input

``````public static bool WorkLoadN(int[,] workload, int max)
{
int start;
int end;
bool underMax = true;
for (int i = rowCount - 1; i >= 0; i--)  // process in reverse order to show it does not need order
{
if (end > rowCount - 1)
end = rowCount - 1;
for (int j = start; j <= end; j++)
}
Debug.WriteLine("");
for (int i = 0; i < rowCount; i++)
{
{
underMax = false;
}
}
return underMax;
}

// this is just the test code to test
{
int rowCount = 20;
int max = 100;
int[,] workload = new int[rowCount, 3];
for (int i = 0; i < rowCount; i++)
{
• well, it says in the question it is UNIX time, so as of right now it is `1484968798`, but it can be future scheduling too, so nothing can prevent it being a really big number. And what about 2.2, 2.2222? Jan 21, 2017 at 3:20