Sunday, 27 September 2020

Merge all overlapping intervals in Java

Merge overlapping intervals in Java.

Given a N pairs of intervals. merge all overlapping intervals..

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

Consider this problem as asking someone availability in their calendar, and if the person calendar is like below,
Meeting from [[1,2],[2,3],[3,4],[10,12]] what the person will say?
I am busy from [1-4] and [10-12], it is like merging intervals that overlaps.

Example of Merging overlapping intervals

merge overlapping intervals

Let see some more input and output:

Example 1: Input: intervals = [[1,2],[2,3],[3,4],[10,15]]
Output: [[1,4],[10,15]]

Example 2: Input: intervals = [[1,5],[3,5],[2,6],[10,15]]
Output: [[1,6],[10,15]]

Example 3: Input: intervals = [[1,4],[2,6]]
Output: [[1,6]]

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).

Our task is to Iterate all the intervals and compare, if there is overlap, just Merge the both intervals into one and expand the endInterval window by comparing endTime of both intervals and consider the one which is highest.

(1, 4), (3, 6), 

Merged Interval = (1, 6)

(7, 9)

totally new range, doesn't overlap with the Merged Interval till now (1, 6)

Put it in our Merged Interval list [(1, 6), (7, 9)] 

(8, 10)

Compare the top interval from merged interval list that is compare (7, 9) with (8, 10)

there is overlap, update the window (7, 10), update the merged interval list (1, 6) (7, 10).

Java Program to Merge overlapping intervals.

    
package javabypatel

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

public class MergeOverlappingIntervals {

    public static void main(String[] args) {
        List<Interval> intervals = Arrays.asList(
                new Interval(1, 2),
                new Interval(2, 3),
                new Interval(3, 4),
                new Interval(10, 15));

        Stack<Interval> mergedIntervals = new MergeOverlappingIntervals().mergeOverlappingIntervals(intervals);
        System.out.println(mergedIntervals);
    }

    public Stack<Interval> mergeOverlappingIntervals(List<Interval> intervals) {
        if (intervals == null) {
            return null;
        }

        Stack<Interval> stack = new Stack<>();
        if (intervals.size() < 2) {
            stack.addAll(intervals);
            return stack;
        }

        Collections.sort(intervals);

        //We can take any data structure which can help us compare the top element.
        stack.add(intervals.get(0));

        for (int i = 1; i < intervals.size(); i++) {
            Interval nextInterval = intervals.get(i);
            Interval resultInterval = stack.peek();

            //Check if Interval overlaps? If yes, increase the end time
            //example (1, 3) (2, 6) -> Intervals overlaps,
            //end time will be max of both end time = 6
            //since the array is sorted by startTime, no need to update the startTime as smallest will be at top.
            if (resultInterval.endTime >= nextInterval.startTime) {
                //update the peek endTime
                resultInterval.endTime = Math.max(resultInterval.endTime, nextInterval.endTime);
            } else {
                //if no overlaps then this is the new range, add it in stack.
                stack.add(nextInterval);
            }
        }

        return stack;
    }
}
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 +
                '}';
    }
}
at

No comments:

Post a Comment