[Solved]: Efficient algorithm for detecting overlaps in time intervals

Problem Detail: 

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.

Asked By : M Miller

Answered By : Alexey Birukov

select * from table where end_time > 12.00PM order by end_time

fetch single row, and check if start_time < 12.00PM.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30492

3.2K people like this

 Download Related Notes/Documents