# Efficient algorithm for detecting overlaps in time intervals

Let's say I am building a time clock app. The employee can log into the interface and then enter time for multiple projects so that we can generate reports for billing as well as payroll.

A table in the database will record the time-in and time-out for each project as a row. A user should be able to sign out and back into the same project multiple times throughout the day, and also can enter time out of order (e.g. sign into Project X at 9:00 AM to 2:00 PM, then into Project Y from 7:00 AM to 8:30 AM).

So let's say my table looks like this:

Project   | Time In | Time Out
----------|---------|---------
Project X | 9.25    | 14.25
Project Y | 7.00    | 8.50

(I am representing the data as a decimal number of hours simply because it's easy to read in the example; the data is actually MySQL TIMESTAMPs.)

Assuming that the data is not in any particular order, I am wondering what would be the simplest and/or most optimized way to validate that the next entry does not conflict with the existing time in such a way that the employee is signed into two projects simultaneously.

e.g. If the user tries to sign in at 12:00 PM or at 7:30 AM, it throws an error because the user was already working on Project X at noon and Project Y at 7:30.

I know I could do this by getting all the time clock data and then detecting if time_in <= input[time] <= time_out, but I'm wondering if there's a cleaner method to accomplish this task.

• "Easiest" as in "what's a small SQL query?" or in "what's a fast algorithm?"? Hint: check out segment trees. (I don't think there's much hope for a non-linear algorithm if you can't do any preprocessing for multiple queries.) – Raphael Oct 2 '14 at 5:18
• I'm not entirely sure, honestly. I'm looking for a balance. Ideally, it'd be the logic unified in a small SQL query, but not if the trade-off is too high. My approach seems poor both in terms of speed and code, since I'd need to fetch all the data and iterate through it. I was wondering if there's a simple way to to do this that I couldn't think of. I will check out segment trees, thanks for the link. – M Miller Oct 2 '14 at 15:21
• Well, the SQL programming part is definitely offtopic here. We might be able to come up with a good conceptual solution which you can then take to Stack Overflow (with your own attempts). That said, if something like a segment tree is the answer, ditching SQL may be advisable (I have no idea how to implement data structures in relational DBs so that they remain efficient). – Raphael Oct 2 '14 at 17:35
• 1. Can you please edit the question to make the question about algorithms, not about SQL? SQL programming (e.g., how to write suitable SQL statements) is off-topic here, and is a matter for StackOverflow. 2. What criteria will you use to evaluate answers? You mention a naive solution in the last sentence of your question. Are you trying to optimize performance? Are you trying to minimize the number of records downloaded from the database? How much better do you need the solution to be, to be acceptable? What's wrong with Raphael's "use segment trees" solution? – D.W. Oct 2 '14 at 21:01

• Heuristically, I'd expect the select statement to return something like half of the entries in the database. Therefore, I'd expect this solution to be about $2\times$ faster than just getting all of the entries and checking which ones satisfy the predicate (which is mentioned in the last sentence of the question and which the author said he doesn't want). I guess only the author can tell us whether this is the sort of solution he was looking for, and whether pulling half of the entries from the database is a big enough improvement over pulling all of the entries from the database. – D.W. Oct 2 '14 at 21:00