Part of our ERP system is a sub-system for running background jobs. We track a variety of meta-data about our jobs in a table including timestamps for submitted, started, and end times.

I'm creating a report showing the performance of our job system, detailed by day. One KPI is maximum # of jobs running at once. The algorithm I'm currently using is:

dim cnt as integer    'number of overlapping jobs
dim max as integer    'maximum number of jobs running at one time

for each Job where 
         Job.SubmitTs = today

  'bJob is a 2nd instance of Job
  for each bJob where
           bJob.SubmitTs =  today and
           bJob.StartTs  <= Job.EndTs and
           bJob.EndTs    >= Job.EndTs
    cnt = cCnt + 1

  if cnt > max then max = cnt

The problem with this algorithm is that it is very slow due to all the looping. I was wondering if there is a faster way to implement this?

Edit I cannot use SQL queries to access the data.

  1. Include all the start and end points (in time) of the Jobs in an array (this creates 2*N elements (1 for start 1 for end))
  2. sort the array ordering by the timestamp of the event,
  3. then iterate over the (2*N) elements as follows:

    for each element X 
      if(X.type == start)
      ans=max(ans, counter);

Complexity: O(n.log(n)) for initial build of the sorted structure + O(n) for the iteration through its elements.

Edit: It has been suggested by Giorgio that an array is used, which is a better option. (The suggestion originally was to use a red/black tree, but no task removing capability seems to be needed, so maintaining order is trivial).

  • 2
    +1: Cool idea! Wouldn't be possible to just sort all the start and end points in an array (this also takes O(n log(n))) and then scan the array as you have described? – Giorgio May 18 '12 at 16:56
  • @Giorgio Actually yes, the OP never says tasks are to be removed, so actually a dynamic array is a better fit. Seems I unconsciously introduced further complexity :) – K.Steff May 18 '12 at 16:58
  • Brilliant! Collapsing it into a single array made it super-fast. – briddums May 18 '12 at 17:34
  • having the array contents already sorted seems like a prerequisite for the algorithm to work at all – matt b Jul 9 '13 at 14:31

SQL knows how to sort stuff, and I'd bet your engine uses the most efficient algorithm it can (i.e. O(n log(n))), while still working if the result set doesn't fit in RAM (in contrast with K.Steff's answer which will fail if the array doesn't fit in RAM). In python :

import sqlite3
connection = sqlite3.connect("database.db")
cursor = connection.cursor()
cursor.execute("SELECT isStart from (" +
               "  SELECT startTime AS time, 1 AS isStart FROM myTable " +
               "  UNION ALL " +
               "  SELECT endTime as time, -1 AS isStart FROM myTable " +
               "  ORDER BY time ASC, isStart ASC" +
maxOverlap = 0
currentOverlap = 0
for (isStart,) in cursor:
    currentOverlap += isStart
    maxOverlap = max(maxOverlap, currentOverlap)
print maxOverlap

Note the isStart ASC order is necessary so the intervals [10,15] and [15,23] are not considered overlapping.

For further improvement, it is probably the case that the columns startTime and endTime have an index, so the SQL engine should efficiently merge the two already sorted tables, resulting in an O(n) operation (the O(log(n)) factor then happens at insertion time for each row, when it is added to the index, but you already have it anyway). If your SQL engine isn't smart enough to do an efficient merge, do it yourself on the fly (still in python) :

import sqlite3
connection = sqlite3.connect("database.db")
cursorStart = connection.cursor()
cursorStart.execute("SELECT startTime FROM myTable ORDER BY startTime ASC")
cursorEnd = connection.cursor()
cursorEnd.execute("SELECT endTime FROM myTable ORDER BY endTime ASC")
maxOverlap = 0
currentOverlap = 0
currentStart = cursorStart.fetchone()
currentEnd = cursorEnd.fetchone()
while currentStart is not None and currentEnd is not None:
    if currentStart < currentEnd:
        currentOverlap += 1
        currentStart = cursorStart.fetchone()
        currentOverlap -= 1
        currentEnd = cursorEnd.fetchone()
    maxOverlap = max(maxOverlap, currentOverlap)
print maxOverlap

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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