CareerCup

This is not an interview question

whats expecte time complexity...is not it just sorting based on start time and then check if for consecutive ranges if start_time_i+1 < stop_time_i

Here's a solution in JavaScript:

//
// Input: [[1,3], [5,7], [2,4], [6,8]]
// Output: [[1,4], [5,8]] (no specific order)
//

/**
 * Do these two ranges overlap?
 *
 * @param {array} a
 * @param {array} b
 * @return {boolen}
 */
var overlaps = function (a, b) {
  return a[0] >= b[0] && a[0] <= b[1]  // a[lo] is in range of b
      || a[1] >= b[0] && a[1] <= b[1]; // a[hi] is in range of b
};

/**
 * Merge two ranges, assuming overlap
 *
 * @param {array} a
 * @param {array} b
 * @return {array}
 */
var merge = function (a, b) {
  return [Math.min(a[0], b[0]), Math.max(a[1], b[1])];
};

/**
 * Merge a single range into a list of ranges
 *
 * @param {array[array]} list
 * @param {array} range
 * @param {array[array]}
 */
var mergeRange = function (list, range) {
  for (var i = 0; i < list.length; i++) {
    if (overlaps(list[i], range)) { // the range overlaps
      var newRange = merge(list[i], range);
      list.splice(i, 1);
      return mergeRange(list, newRange); // recursive call
    }
  }
  list.push(range); // the range doesn't overlap, so just add it to list
  return list;
};

/**
 * Merge a list of ranges into each other
 *
 * @param {array[array]} ranges
 * @return {array[array]}
 */
var mergeRanges = function (ranges) {
  return ranges.reduce(function (acc, curr) {
    return mergeRange(acc, curr);
  }, []);
};

O(nlogn) solution: thinking about ranges as if they were representing start and end of an event. With this in mind, sorting starts end ends 'event's separately. Then counting 'start' and 'end' of 'event's, if count is larger than 1 at some point, this would mean at least 2 ranges overlap.

public static boolean checkOverlap(int[][] ranges) {
		if (ranges == null || ranges.length <=0) {
			return false;
		}
		
		int[] starts = new int[ranges.length];
		int[] ends = new int[ranges.length];
		
		for (int i = 0; i<ranges.length; i++) {
			starts[i] = ranges[i][0];
			ends[i] = ranges[i][1];
		}
		
		Arrays.sort(starts);
		Arrays.sort(ends);
		
		int count = 0;
		int s = 0;
		int e = 0;
		while (e<ranges.length) {
			if (s<ranges.length && starts[s] == ends[e]) {
				return true;
			} else {
				if (s<ranges.length && starts[s] < ends[e]) {
					count++;
					if (count > 1) {
						return true;
					}
					s++;
				} else {
					count--;
					e++;
				}
			}
		}
		
		return false;
	}

import java.util.Arrays;

class Coordinate implements Comparable<Coordinate>{
int x;
int y;
Coordinate(int x,int y){
this.x=x;
this.y=y;
}

public int compareTo(Coordinate e2) {

int x=((Coordinate)e2).x;
return this.x-x;
}

}


public class TimeInterval {

public static void main(String[] args) {
// TODO Auto-generated method stub


Coordinate[] c=new Coordinate[4];
c[0]=new Coordinate(1,3);

c[1]=new Coordinate(5,7);

c[2]=new Coordinate(2,4);

c[3]=new Coordinate(6,8);


Arrays.sort(c);
boolean set=false;
for(int i=0;i<3;i++){
if((c[i].y)>(c[i+1].x)){
set=true;
//System.out.println("overlap");
}


}
if(set){
System.out.println("overlap");
}else{
System.out.println("Not overlap");
}




}

}
Time complexity:O(nlogn)