w3resource

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

Java Basic: Exercise-140 with Solution

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.

Java Code Editor:

Company:  LinkedIn Google Facebook Microsoft Bloomberg Yelp Twitter

Previous: Write a Java program to get the index of the first number and the last number of a subarray where the sum of numbers is zero from a given array of integers.
Next: Write a Java program to check if a given string has all unique characters

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Become a Patron!

Follow us on Facebook and Twitter for latest update.

It will be nice if you may share this link in any developer community or anywhere else, from where other developers may find this content. Thanks.

https://www.w3resource.com/java-exercises/basic/java-basic-exercise-140.php