Multiple “intervals” are to be given as tasks. Calculate the maximum work time (minutes) to assign to one worker

Implement the method “int Problem2#getMaxWorkingTime(List intervals)”.

Return the maximum time to work on a task when one worker takes it.

Time assignment unit shall be based on tasks. (i.e. Task assignment shall be either to complete the whole task, or to do nothing for it.)

The length of the interval, time required to complete the task, is calculated by subtracting "end time" from "start time". (e.g. If [12:00, 13:00] is given, the length of the task is 60 min.)

Return 0 if the argument is null or an empty list.

The argument (a list of “intervals”) must not contain null.

The number of “intervals” must not exceed 10,000

In Figure 3 , work time is maximized when three tasks [“06:00”, “08:30”], [“09:00”, “11:30”], and [“12:30”, “14:00”], are assigned. Therefore, the answer is 390 (minutes).

Intervals = [06:00-08:30], [08:00-09:00], [09:00-11:00], [09:00-11-30], [12:30-14:00], [10:30-14:00] (which is shown in figure 3 also)
Total Intervals = 6

What I have tried so far

To me it appears to as a problem whose answer I can find simply by subtracting the Interval with max end-time i.e 14:00 with Interval which has smallest start-time, say 14:00 minus 06:00 answer is 480 minutes (since 6 to 14 has 8 hours in it so 8*60 minutes = 480 minutes) but the correct answer is 390 minutes

Can any one please help me explaining how to solve this problem...?

The thing which I want to understand is out of 6 Intervals why only those 3 Intervals (mentioned above) is selected ?

I don't understand the illustration, but from the example it appears that the work time is calculated as a summation of the times of each of the individual work items.
[“06:00”, “08:30”] = 150 mins
[“09:00”, “11:30”] = 150 mins
[“12:30”, “14:00”] = 90 mins
Work time = 150 + 150 + 90 = 390 mins

In your solution you are just taking the time duration from beginning the first task and finishing the last task, which I assume is incorrect because there is no work being done inbetween each task.

naved momin wrote:
The thing which I want to understand is out of 5 Intervals why only those 3 Intervals (mentioned above) is selected ?

5 intervals? Your post only refers to the 3 I've just discussed. What are the other 2?

It is preferred if you do not go back and significantly edit your original posts as in this case it now looks like I wasn't paying attention and hadn't read your post properly. Now it doesn't bother me much so you're ok but other users on this forum might not like it. So my suggestion for future reference is to leave your posts as they are and think of it as a discussion, where you clear up any questions in new posts.

This looks a bit like a homework, or a tutorial question. We are more than happy to help you but we do ask that you QuoteYourSources (<- click link) and tell us where you got this question from (It's a copyright thing so please treat this request with importance)

Anyway, back to the discussion: Your question was about how you derived 390 where you got 480. Do you still have a question about this?

Fist I m very sorry i didnt knew that editing my orignal post will have that impact, i will keep this thing in mind

Second thing is this question is asked to me in one of mine interview

Third ya still i dont know how to solve this problem by hands (because then only I can code it)

I have already spent hours trying to figure it out how this problem might me solved but no luck, so asked here, I guess there is some math involved in this type of questions so unless and until i don't have that particular topic of maths knowledge I wont be able to solve it.

Well, here's an explanation of why the answer is 390 minutes.

The calculation you've made - earliest start time to last end time - gives you an upper bound on the solution. But there's no way of reaching that upper bound, because that would mean someone working 100% of the time: maximum efficiency. For example, at 12:00 there's only one task available, so they'd have to be working on that. But then there's no way they can be working on a task at 10:00, because those tasks both overlap with the one you've already allocated, The big constraints are that you can only work on one at a time, and once you've started a task you have to complete it.

So the problem is to find the selection of tasks that minimises the gaps where you aren't working. The best solution here is the one that is working for 390 minutes.

You might try this as an initial attempt at an algorithm. It works in this particular case, but it doesn't in the general case:

- Allocate the earliest starting task
- Move forward in time to the end of that task
- Allocate the next task to start (pick the first one if more than one)
- Keep going until there are no more tasks to allocate.

Can you see why that doesn't always work? Consider this example:

That algorithm would pick tasks A and C, but picking B is actually more efficient.

I think I can see a way of solving the general case, though it isn't simple and I'm not certain there isn't a better way. Half the battle in some of these problems is working out the right way to represent the problem. My idea is to represent the problem as a weighted directed graph:

- Each task is a node, and we also add Start and End nodes.
- We add an edge from the Start to every task node, and from every task node to the end node
- We also add an edge from every node to every other node that can follow it
- The weights of each edge are the duration of the task that the edge points towards (and zero for the End edges).

So now any path through the graph from Start to End is a valid selection of tasks, and the sum of the edge weightings on that path is the total work time. So the problem is to maximise this sum. So it's a Longest Path problem. That isn't straightforward, but it is a standard graph problem* with some established algorithms, if you're familiar with those.

(* Well, Shortest Path is a standard graph algorithm, but if you negate all the weightings it's equivalent, as long as you're using an algorithm that can cope with negative weights).

My guess is that the intervals were assigned to workers in order:
- A goes to worker 1.
- B overlaps A so it has to go to worker 2.
- C doesn't overlap A, so it can go to 1.
- D overlaps both B* and C, so it has to go to worker 3.
- E fits with worker 1
- F works with 2.

* Does D, which starts at 9, necessarily overlap B, which ends at 9? IT doesn't really matter. You'll need three workers anyways, since there are three active intervals at 10:45

If you arrange them like this:

the top line shows the maximum worker usage A + D + E = 150 + 150 + 90 = 390.

Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1013

3

posted

0

Ryan McGuire wrote:
the top line shows the maximum worker usage A + D + E = 150 + 150 + 90 = 390.

But what algorithm would you use to determine that loading worker 1 with A, D and E is better than A, C and E? You could use a brute force algorithm that assigns intervals to workers in various orders (ABCDEF, ABCDFE, ABCEDF, etc.) and keep track of which order yielded the best answer. Surely there's a better way, which I would hope is more efficient than O(n!)

Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.

Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1013

3

posted

0

Matthew Brown wrote:
I think I can see a way of solving the general case, though it isn't simple and I'm not certain there isn't a better way. Half the battle in some of these problems is working out the right way to represent the problem. My idea is to represent the problem as a weighted directed graph:

- Each task is a node, and we also add Start and End nodes.
- We add an edge from the Start to every task node, and from every task node to the end node
- We also add an edge from every node to every other node that can follow it
- The weights of each edge are the duration of the task that the edge points towards (and zero for the End edges).

So now any path through the graph from Start to End is a valid selection of tasks, and the sum of the edge weightings on that path is the total work time. So the problem is to maximise this sum. So it's a Longest Path problem. That isn't straightforward, but it is a standard graph problem* with some established algorithms, if you're familiar with those.

(* Well, Shortest Path is a standard graph algorithm, but if you negate all the weightings it's equivalent, as long as you're using an algorithm that can cope with negative weights).

Matthew, maybe a Shortest Path algorithm is the way to go. Just adjust how the edge lengths are determined.

As you mentioned, treat the intervals as nodes. Also add two artificial nodes, "start" and "end", where "start" ends when the earliest-starting interval starts, and "end" starts when the latest-ending interval ends. However, the "distance" between any two nodes is the time between the end of the earlier one and the start of the later one. If the later node starts before the earlier one ends, then there is not path between those two nodes.

The shortest path from "start" to "end" is start->A->D->E->end = 0 + 30 + 60 + 0 = 90.* 90 turns out to be the total "idle" time between tasks done by a maximally-employed worker. To get the work done by that worker, you can either A) add up the lengths of the intervals on the shortest path or B) subtract the total path "distance" from the distance between "start" and "end" (480-90 = 390).

If you need to create the entire chart of who does what, just repeat the process with the used nodes removed. i.e. Find the shortest path between start and end without A, D and E included. Repeat until all the intervals are used.

* I'll leave the implementation of the best Shortest Path algorithm as an exercise for the interested reader.