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

Question

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

Problem: write a function to tell whether a series of workloads will exceed 
         the maximum workload or not

Input: MaxWorkLoad: example 10
       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)]
       The workload will "add up", so a 3 and 2 will add up to 5
                                           
Output: a boolean indicating whether the series of workload can fit in without
        exceeding MaxWorkLoad 

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[2] = 3 and dict[6] = -3.

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

(and actually, if we treat the time endpoint as inclusive, then we won't have dict[8] = -2 but have dict[9] = -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[2] as 3, add 3 to CurrentWorkLoad, and when you see dict[3], add the 2 to CurrentWorkLoad, and when you see dict[6], 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[6] is -3, and when you see (6, 8, 1), then dict[6] += 1 and becomes -2.

So if in JavaScript, it is like

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

dict[endTime] ||= 0; 
dict[endTime] -= workload;

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)?

Answer 1

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.

Answer 2

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). (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[123] 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).

Answer 3

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.

Answer 4

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 
         the maximum workload or not

Input: MaxWorkLoad: example 10
       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)]
       The workload will "add up", so a 3 and 2 will add up to 5

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

My code

drop schema if exists t1 cascade;
create schema t1;
set search_path='t1';
create table segment
(
    start_dt bigint,
    end_dt bigint,
    load 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
        raise info 'add % % % ($1)', xr1.start_dt, $1, xr1.load;
        raise info 'add % % % ($1)', $1, xr1.end_dt, xr1.load;
        insert into segment values 
            ( xr1.start_dt, $1, xr1.load ),
            ( $1, xr1.end_dt, xr1.load );   

        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
        raise info 'add % % % ($2)', xr2.start_dt, $2, xr2.load;
        raise info 'add % % % ($2)', $2, xr2.end_dt, xr2.load;
        insert into segment values 
            ( xr2.start_dt, $2, xr2.load ),
            ( $2, xr2.end_dt, xr2.load );

        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
        load = load + $3
    where
        start_dt >= $1 and end_dt <= $2
    ;
    
end
$$ language 'plpgsql';

select segment_add(0,4000,6000);
select segment_add(1000,10000,5000);
select segment_add(12000,15000,5000);
select segment_add(13000,14000,6000);
-- the answer should have 0-1 1-4 4-10 12-13 13-14 14-15
select * from segment order by start_dt;

Answer 5

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.

• add field is_started=false
• Sort by start time
• foreach item in queue
  • if not item.is_started
    • increment load (+ item.load)
    • mark item as started
    • reinsert in queue, key on appropriate-time (end_time if is_started else start_time)
  • else
    • decrement load (- item.load)
    • discard item
  • check load

This is algorithm to solve your problem.

Answer 6

O(n)

Pretty simple

• Create an array for load for each slot
• Read the input and add the 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 rowCount = workload.GetLength(0);
    int colCount = workload.GetLength(1);
    int[] loadNet = new int[rowCount];
    int start;
    int end;
    int load;
    bool underMax = true;
    for (int i = rowCount - 1; i >= 0; i--)  // process in reverse order to show it does not need order
    {
        start = workload[i, 0];
        end = workload[i, 1];
        if (end > rowCount - 1)
            end = rowCount - 1;
        load = workload[i, 2];
        for (int j = start; j <= end; j++)
            loadNet[j] += load;
    }
    Debug.WriteLine("");
    for (int i = 0; i < rowCount; i++)
    {
        Debug.WriteLine("loadNet[{0}] {1}", i, loadNet[i]);
        if (loadNet[i] > max)
        {
            Debug.WriteLine("max exceeded loadNet[{0}] {1}", i, loadNet[i]);
            underMax = false;
        }
    }
    return underMax;
}

// this is just the test code to test
public static void WorkLoadTestN()
{ 
    int rowCount = 20;
    int max = 100;
    int[,] workload = new int[rowCount, 3];
    for (int i = 0; i < rowCount; i++)
    {
        workload[i, 0] = i;
        workload[i, 1] = i + rand.Next(1, max / 6);
        workload[i, 2] = rand.Next(max / 4);
        Debug.WriteLine("intput start {0}  end {1}  load {2}", i, workload[i, 1], workload[i, 2]);
    }
    bool underMax = WorkLoadN(workload, max);
}