Problem

Given a set of intervals, find out if any two intervals overlap.

Example:

1
2
3

Intervals:[[1,4], [2,5], [7,9]]
Output: true
Explanation: Intervals [1,4] and [2,5] overlap

Solution

Method 1 - Sorting

Let’s take the example of two intervals (‘a’ and ‘b’) such that a.start <= b.start. There are three possible scenarios:

  1. ‘a’ and ‘b’ do not overlap.
  2. Some parts of ‘b’ overlap with ‘a’.
  3. ‘a’ fully overlaps ‘b’.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

public static boolean doesOverlap(Interval[] intervals) {
	if (intervals.length < 2) {
		return false;
	}
	Arrays.sort(intervals, (a, b) -> a.start - b.start);
 
    for(int i=0; i<intervals.length-1; i++){
        if(intervals[i].end>intervals[i+1].start){
            return true;
        }
    }
 
    return false;
}
 
1
2
3
4
5
6


Arrays.sort(intervals, new Comparator<Interval>(){
	public int compare(Interval a, Interval b){
		return a.start-b.start;
	}
});

Complexity

  • ⏰ Time complexity: O(n*logn)
  • 🧺 Space complexity: O(n)