How to check if two or more time periods overlap each other in c++?

Question

I am using std::pair to get start time and end time of each time periods and I put all those time periods in an array (say classes[no_of_time_periods]). Code for it:

int getClassTimes(int N)
{
   int subsets, startTime, endTime;
   std::pair<int,int> classes[N];
   for(int i=0;i<N;i++)
   {
       printf("Please Enter Class %d Start Time and End Time:",(i+1));
       scanf("%d",&startTime);
       scanf("%d",&endTime);
       classes[i] = std::make_pair(startTime,endTime);
   }
   subsets = compute(classes,N);
   return subsets;
}

I know I can check if two time periods overlap or not using following condition:

if(!(classes[i].first<classes[j].second && classes[i].second>classes[j].first))

But I want to check for more than two time periods. Example:

Input:
No_Of_Time_Periods = 5
Time_Period 1      = 1 to 3
Time_Period 2      = 3 to 5
Time_Period 3      = 5 to 7
Time_Period 4      = 2 to 4
Time_Period 5      = 4 to 6

Calculation(Number of subsets of non-overlapping Time Periods):
**Note: If end time of one class is start time of other, they are non-overlapping.
Ex((1 to 3) and (3 to 5) are non-overlapping.)**

(1 to 3)(3 to 5)
(1 to 3)(3 to 5)(5 to 7)
(1 to 3)(4 to 6)
(1 to 3)(5 to 7)
(2 to 4)(4 to 6)
(2 to 4)(5 to 7)
(3 to 5)(5 to 7)

Output:
Total Number of subsets of non-overlapping classes:7

I found the logic and I wrote the code.But while submitting in Online Judge(SPOJ), it says "Time Limit Exceeded".So, Obviously my code was not well optimized. How to achieve this using c++ with better performance? Any Help would be appreciated. Thanks in advance!

[getchar_unlocked( ) VS scanf() VS cin](http://stackoverflow.com/questions/9052757/getchar-unlocked-vs-scanf-vs-cin) — Arun A S, Mar 23 '15 at 07:49
code optimization belongs on [Code Review](http://codereview.stackexchange.com/) Read [What topics can I ask about here?](http://stackoverflow.com/help/on-topic) and [How do I ask a good question?](http://stackoverflow.com/help/how-to-ask) — Arun A S, Mar 23 '15 at 07:53
oh I tried everything. getchar_unlocked() instead of scanf. I used inline functions and register variables wherever necessary. But still Time Limit Exceeded!!! Itseems logic part must be modified in a better way. for example if we are trying to find overlap or not for some 10000 time periods, it must process it in a faster way to find the result. — Nantha Kishor Anandhan, Mar 23 '15 at 07:58
and this question is nowhere in the stackoverflow. only if two time periods overlap or not exists in stackoverflow. — Nantha Kishor Anandhan, Mar 23 '15 at 07:59
It sounds like you would compare every interval to every other interval => O(n^2). You can do this in O(n log n) as the most expensive operation is sorting your pairs... — wiseveri, Mar 23 '15 at 08:02
As noted; if you sort your pairs first on start time, then on end time, you can find all overlaps in a single pass over the array after that. — Tomas Aschan, Mar 23 '15 at 08:36
Hi @Wiseveri...Exactly that is what I wanted. I wanted to do in O(n log n) instead of O(n^2). But that logic doesn't strike, though I thought a lot about it. could you explain it how to do it? — Nantha Kishor Anandhan, Mar 23 '15 at 09:10
Hi @Tomas...Ya I sorted and then only I proceeded with my logic. but still how could you find all overlaps in a single pass? could you explain it a bit? — Nantha Kishor Anandhan, Mar 23 '15 at 09:10
You'd be better off discussing this with the people in your algorithm class. As far as I remember you sort by end time and check if the next element started before the current ends.. — wiseveri, Mar 23 '15 at 13:06

Barmak Shemirani · Answer 1 · 2015-03-23T08:42:11.620

1

This is so confusing! The overlap test should be like so:

if ((classes[i].second < classes[j].first) || (classes[i].first > classes[j].second))
  printf("no overlap");

if (!((classes[i].second < classes[j].first) || (classes[i].first > classes[j].second)))
  printf("overlap");

assuming classes[n].first is always less than classes[n].second

edited Mar 23 '15 at 08:42

answered Mar 23 '15 at 08:16

Barmak Shemirani

30,904
6
40
77

score -1 · Answer 2 · answered Mar 23 '15 at 09:07

-1

check out interval trees. You will get logarithmic complexity: http://en.wikipedia.org/wiki/Interval_tree

answered Mar 23 '15 at 09:07

Sergei Vorobiev

364
2
8

Hi @Sergei , Thanks for your answer. I searched a lot in the net. I could not figure out anything related to this. But the answer you suggested truly helps. But still I could not get that fully. Could you explain that logic a bit using c++? – Nantha Kishor Anandhan Mar 23 '15 at 09:37

How to check if two or more time periods overlap each other in c++?

2 Answers2