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

Last update on December 21 2024 09:34:05 (UTC/GMT +8 hours)

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:

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