Home » Interviews » Find overlapping interval among a given set of intervals.

Find overlapping interval among a given set of intervals.

in - on 22:44:00 - No comments

Find overlapping interval among a given set of intervals.

Given a N pairs of intervals. Identify interval that overlap with other interval.

You are given a pair of intervals in a format (start time, end time), find interval that overlaps with other interval.

Example of overlapping intervals

find overlapping time intervals

Let see some more input and output:

Example 1:
Input: (1, 3) (3, 5) (5, 7)
Output: No overlapping Intervals.

Example 2: (2, 3) (3, 5) (1, 6)
Output: (1, 6) overlaps with (2, 3)
Though (3, 5) also overlaps with (1, 6) we are mainly looking for one of them. Given solution below find one of them. 

Algorithm

Lets say we are given below time intervals

(1, 4), (7, 9), (3, 6), (8, 10)

If we sort the time intervals based on start time,

(1, 4), (3, 6), (7, 9), (8, 10)

If we see the first two interval, end time of first interval is greater than start time of second interval which means there is overlap of (end time - start time) in this case it is (4 - 3) = overlap of 1 unit.

Our task is to just find the overlapping intervals.

Java Program to find overlapping intervals among a given set of intervals.

package javabypatel;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class OverlappingIntervals {
    public static void main(String[] args) {
        List<Interval> intervals = Arrays.asList(
                new Interval(1, 3),
                new Interval(6, 8),
                new Interval(2, 4),
                new Interval(5, 6));
        List<Interval> interval = new OverlappingIntervals().findOverlappingIntervalApproach1(intervals);
        System.out.println("Overlapping intervals :" + interval);

        boolean isOverlappingIntervals = findOverlappingIntervalApproach2(intervals);
        System.out.println("Is overlapping intervals :" + isOverlappingIntervals);
    }

    //Sort the intervals by start time and compare the endtime of first interval with the start time of next interval.
    //If the endTime of first interval is > then startTime of next interval means there is overlap
    //Example: [(1, 3) (2, 4)]
    //time complexity: (n log n) + n = (n log n)
    public List<Interval> findOverlappingIntervalApproach1(List<Interval> intervals) {
        Collections.sort(intervals); //(n log n)
        List<Interval> overlappingInterval = new ArrayList<>();

        for (int i = 0; i < intervals.size()-1; i++) { //n
            if (intervals.get(i).endTime > intervals.get(i+1).startTime) {
                overlappingInterval.add(intervals.get(i));
                overlappingInterval.add(intervals.get(i+1));
            }
        }
        return overlappingInterval;
    }

    //Another approach which just says there is overlap or not.
    //time complexity:
    // O(n) = to find the max element in array
    // O(m) = where m is the max element in array
    // Total = O(m + n)
    // this approach works well when the range is small
    public static boolean findOverlappingIntervalApproach2(List<Interval> intervals){
        //find the highest end time within list of all intervals
        int highestTime = intervals.get(0).endTime;
        for (int i = 1; i<intervals.size(); i++) {
            int endTime = intervals.get(i).endTime;
            if(highestTime < endTime)
                highestTime = endTime;
        }

        int[] count = new int[highestTime + 1];
        //Mark the count[startTime] to +1 and count[endTime] to -1
        for (int i = 0; i<intervals.size(); i++) {
            Interval current = intervals.get(i);
            count[current.startTime]++;
            count[current.endTime]--;
        }

        //Iterate count array and sum the values
        //if at any point sum is > 1 that means interval overlaps.
        boolean isOverlappingIntervals = false;

        int sum = 0;
        for (int i = 0; i <count.length; i++) {
            sum += count[i];
            if(sum > 1){
                isOverlappingIntervals = true;
                break;
            }
        }

        return isOverlappingIntervals;
    }
}
Interval.java 
package javabypatel;

public class Interval implements Comparable<Interval>{
    public int startTime;
    public int endTime;

    public Interval(int startTime, int endTime) {
        this.startTime = startTime;
        this.endTime = endTime;
    }

    @Override
    public int compareTo(Interval interval) {
        if (startTime < interval.startTime) {
            return -1;
        } else if (startTime == endTime) {
            return 0;
        } else {
            return 1;
        }
    }

    @Override
    public String toString() {
        return "Interval{" +
                "startTime=" + startTime +
                ", endTime=" + endTime +
                '}';
    }
}
Approach 2

In this approach, we are going to take a count array and for each given interval start time we will do count[startTime]++ and for end time, do count[endTime]--.

After filling the count array, iterate count array and do the sum of counts, If at any given index we find 
sum > 2 it means there is overlapping intervals. 

How this approach is working? say if we have intervals as (1, 3) and (2, 5), and count array for this will be. array size will be 5(highest end time in given intervals)
(1, 3) = [0, 1, 0, -1, 0,  0]
(2, 5) = [0, 1, 1, -1, 0, -1]

Whenever we see adjacent one's, it means there is y interval(in this case (2,5)) which has starting time before the end of x interval(1,3).
 
Categories:

Post a Comment