# Job scheduling: algorithm to find the maximum number of overlapping jobs?

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.

• 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 '16 at 20:22

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.
• @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 '16 at 17:13