2

Problem: you are given n jobs, each of which has a start and an end time. The task is to simply output the maximum number of active jobs (ones that overlap with one another, inclusive), and to return the time range of overlapping jobs.

For example (format: job = start, end):

J1 = 0, 1
J2 = 1, 1.2
J3 = 2, 2.5
J4 = 0.3, 0.7
J5 = 1.5, 2
J6 = 0.5, 1

Would have two overlapping ranges: 

0 to 1.2, with four jobs (J1, J2, J4, J6)
1.5 to 2.5 with two jobs (J3, J5)

The first overlapping range would be the solution -- 4 overlapping jobs with a time range of 0 to 1.2.

As you can see, the input may or may not be sorted, which is problematic for performance reasons. I am wondering if there is a standard algorithm for this problem because I am given a very large string that I have to process and find jobs that overlap.

My current approach is to treat it like an online problem, and therefore read the start and end times, then store it into a hashmap, and afterwards just read the rest of the inputs and if it falls in an existing interval, append it to the values, then change the end time if the end time is greater than the previous end time.

Am I on the right track? Thanks so much.

Improve this question
1
  • As you are asking if you're on the right track, I'd suggest that you write your algorithm in a bit more detail, such as in terms of loops or nested step so you can determine the complexity. (For example, if you are doing two loops, nested, over the input, that is O(n^2).) I think this can be done linearly, after sorting, which is usually ~O(n log n).
    – Erik Eidt
    Sep 12, 2016 at 20:22

1 Answer 1

Reset to default
6

Put the start and end points of the job intervals into an array (together with the information to which job they belong, and if the entry is a start point or an end point). Then sort those items (in O(n*log n) time). Afterwards, it will be possible to determine the number (and the set) of overlapping jobs at any time by a linear scan through the sorted array: whenever a new interval starts, add the corresponding job to the set of active jobs. Whenever an interval ends, remove the corresponding one from the set.

That way, you can easily determine groups of jobs which are overlapping or non-overlapping (there must be a point in time where no job is active if two groups are separate), or the maximum number of simultaneous jobs (which is not what you asked for, but maybe of interest either).

I think this algorithm belongs to the class of sweep line algorithms.

Improve this answer
4
  • What if A overlaps B and B overlaps C but A does not overlap C ?
    – kevin cline
    Sep 12, 2016 at 21:15
  • @kevincline: the OPs example showed clearly his intention was to combine A, B, and C in one group for this case (note J2 and J4 do not overlap). In graph terms, the task is to find a connected subgraph, not a fully connected subgraph. And that is what the algorithm described in my answer does.
    – Doc Brown
    Sep 13, 2016 at 9:24
  • @DocBrown This is a very efficient method... Basically push active jobs to a data structure, and then remove the job associated with an endpoint from the active jobs when an endpoint is reached when iterating over all the intervals. Although I am wondering with this method, how would one distinguish between a start or end point? Because previously I had two arrays to distinguish between the two... Anyway, I'm sure I'll figure it out, thanks a lot!
    – Liz
    Sep 13, 2016 at 15:21
  • @Liz: of course, you need to put triplets (time, isStartOrEndpoint, jobnumber) into the array, where isStartOrEndpoint is a boolean flag indicating the type.
    – Doc Brown
    Sep 13, 2016 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.