Algorithm for finding overlapping times

Question

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
  next

  if cnt > max then max = cnt
next

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.

Answer 1

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 
   do 
     if(X.type == start)
       counter++
     else
       counter--
     ans=max(ans, counter);
   end
   

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

Answer 2

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()
    else:
        currentOverlap -= 1
        currentEnd = cursorEnd.fetchone()
    maxOverlap = max(maxOverlap, currentOverlap)
print maxOverlap