Friday, May 15, 2015

Synopsys Question: Check if any two intervals overlap among the given n intervals

Problem: Given n intervals, each interval having start and end time, check if any two intervals overlap or not.

  1. Sort all intervals according to their start time.
  2. In the resultant sorted array, if start time of current interval is less than end of previous interval, then there is an overlap.

struct Interval
int start;
int end;

bool compareInterval(Interval i1, Interval i2)
return i1.start < i2.start ? true : false;

bool isOverlap(Interval *arr, int len)
if(arr == 0 || len == 0)
return false;

std::sort(arr, arr + len, compareInterval);
for(int i = 1; i < len; ++i)
if(arr[i].start < arr[i-1].end)
return true;
return false;

Complexity: O(nlogn)

No comments:

Post a Comment