Checking the overlap between given time duration[reviewed]

Problem

You are given the list of time duration as below:

 (3, 4),  (10, 13), (5, 6), (5, 7)), (7, 9)

Your algorithm should be able to tell whether there is overlap among these time durations. 

This problem is similar to "Counting room" problem but the algorithm is simpler.

1) Sort the time durations by start time. O (N log N)
2) Iterate over the list and check if the preceding time duration's end time is larger than next duration's start time. If so, there is overlap. O (N)

Overall running time is O(N log N).

Here is the complete solution in C++


Practice statistics

16:19.96 : to write up the code. (silly choice of struct name, extent cause the syntax error but the algorithm was sound)

UPDATE(2019-07-26): solved the problem again. This time, I used a matrix since the unit is hours. There is only 24 hrs.  Overall running time is close to O(N), where N is # of durations.

Here is a solution in python:


Practice statistics

4:00: for algorithm
6:00: to write the code and test cases(no error yay!!)

Comments

Popular posts from this blog

Planting flowers with no adjacent flower plots

Find the maximum number of bomb that can be detonated