w3resource

Java: Merge all overlapping Intervals from a given a collection of intervals


Merge Overlapping Intervals

Write a Java program to merge all overlapping intervals from a given collection of intervals.

Sample Solution:

Java Code:


import java.util.*;

public class Solution
{   
    public static void main (String[] args) throws java.lang.Exception
    {
        // Create an ArrayList of Interval objects
        ArrayList<Interval> x = new ArrayList<>();

        // Add intervals to the ArrayList
        x.add(new Interval(1, 3));
        x.add(new Interval(2, 6));
        x.add(new Interval(8, 10));
        x.add(new Interval(15, 18));
        x.add(new Interval(17, 20));

        // Merge overlapping intervals
        x = merge(x);

        // Print the merged intervals
        for(Interval i : x)
        {
            System.out.println(i.getStart() + " " + i.getEnd());
        }
    }

    public static ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        // Check for the number of intervals
        if(intervals.size() == 0 || intervals.size() == 1)
            return intervals;

        // Sort the intervals based on the start values
        Collections.sort(intervals, new IntervalComparator());

        // Initialize the variables
        Interval first = intervals.get(0);
        int start = first.getStart();
        int end = first.getEnd();

        // Create a list for the merged intervals
        ArrayList<Interval> result = new ArrayList<Interval>();

        // Merge overlapping intervals
        for (int i = 1; i < intervals.size(); i++) {
            Interval current = intervals.get(i);
            if (current.getStart() <= end) {
                end = Math.max(current.getEnd(), end);
            } else {
                result.add(new Interval(start, end));
                start = current.getStart();
                end = current.getEnd();
            }
        }

        // Add the last merged interval
        result.add(new Interval(start, end));
        return result;
    }
}

class Interval 
{
    private int start;
    private int end;

    Interval() {
        start = 0;
        end = 0;
    }

    Interval(int s, int e) 
    {
        start = s;
        end = e;
    }

    public int getStart() {
        return start;
    }

    public int getEnd() {
        return end;
    }
}

class IntervalComparator implements Comparator<Interval>
{
    public int compare(Interval i1, Interval i2)
    {
        // Compare intervals based on start values
        return i1.getStart() - i2.getStart();
    }
} 

Sample Output:

1 6
8 10
15 20

Flowchart:

Flowchart: Java exercises: Merge all overlapping Intervals from a given a collection of intervals.


For more Practice: Solve these Related Problems:

  • Write a Java program to count the minimum number of intervals needed to cover all given intervals after merging.
  • Write a Java program to merge overlapping intervals while keeping track of the number of original intervals within each merged range.
  • Write a Java program to find the interval that is overlapped the most in a given list of intervals.
  • Write a Java program to determine the maximum number of non-overlapping intervals that can be selected from a given list.

Go to:


PREV : Subarray with Zero Sum.
NEXT : Check Distinct Characters.


Java Code Editor:

Company:  LinkedIn Google Facebook Microsoft Bloomberg Yelp Twitter

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Follow us on Facebook and Twitter for latest update.