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++

	#include<vector>
	#include<iostream>
	#include<algorithm>
	using namespace std;
	struct range {
	int start;
	int end;
	range(int s, int e): start(s), end(e) {}
	};
	bool compare(range* prev, range *next)
	{
	return prev->start < next->start;
	}
	bool is_overlap(vector<range *>& input)
	{
	sort(input.begin(), input.end(), compare);
	range* prev = input[0];
	for(int i = 1; i < input.size(); i++)
	{
	range * cur = input[i];
	if (prev->end > cur->start)
	return true;
	prev = cur;
	}
	return false;
	}
	int main ()
	{
	vector<range *> input;
	input.push_back(new range(3, 4));
	input.push_back(new range(10, 13));
	input.push_back(new range(5, 6));
	input.push_back(new range(5, 7));
	input.push_back(new range(7, 9));
	cout<<" overlap = " << is_overlap(input)<<endl;
	return 1;
	}

view raw check_if_time_overlap.cpp hosted with ❤ by GitHub

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:

	class OverlapChecker:
	def check(self, list):
	matrix = [ 0 for i in range(24)]
	for duration in list:
	for h in range(duration[0], duration[1]):
	if matrix[h] == 1:
	return True
	matrix[h] = 1
	return False
	checker = OverlapChecker()
	input = [[3, 4], [10, 13], [5, 6], [5, 7], [7, 9]]
	print("input = {} is_overlap = {}".format(input, checker.check(input)))
	input = [[3, 4], [10, 11], [5, 6], [7, 9], [12,14]]
	print("input = {} is_overlap = {}".format(input, checker.check(input)))

view raw time_overlap_checker.py hosted with ❤ by GitHub

Practice statistics

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