Merge Overlapping Intervals

Question

Question : Given a set of time intervals in any order, merge all overlapping intervals into one and output the result which should have only mutually exclusive intervals. Let the intervals be represented as pairs of integers for simplicity. For example, let the given set of intervals be {{1,3}, {2,4}, {5,7}, {6,8} }. The intervals {1,3} and {2,4} overlap with each other, so they should be merged and become {1, 4}. Similarly {5, 7} and {6, 8} should be merged and become {5, 8}

Write a function which produces the set of merged intervals for the given set of intervals.

My code:

import java.util.*;
import java.lang.*;
import java.io.*;

class Interval 
{
    int start;
    int end;

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

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

class Ideone
{
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {

        if(intervals.size() == 0)
            return intervals;
        if(intervals.size() == 1)
            return intervals;

        Collections.sort(intervals, new IntervalComparator());

        Interval first = intervals.get(0);
        int start = first.start;
        int end = first.end;

        ArrayList<Interval> result = new ArrayList<Interval>();

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

        }

        result.add(new Interval(start, end));

        return result;

    }
}

class IntervalComparator implements Comparator
{
    public int compare(Object o1, Object o2)
    {
        Interval i1 = (Interval)o1;
        Interval i2 = (Interval)o2;
        return i1.start - i2.start;
    }
}
public static void main (String[] args) throws java.lang.Exception
{
    ArrayList<Interval> x = new ArrayList<Interval>();
    Interval i1 = new Interval(1,3);
    Interval i2 = new Interval(2,6);
    Interval i3 = new Interval(8,10);
    Interval i4 = new Interval(15,18);

    x.add(i1);x.add(i2);x.add(i3);x.add(i4);

    ArrayList<Interval> r = merge(x);

    for(Interval i : r)
    {
        System.out.println(i.start+" "+i.end);
    }

}
}

These are the errors which i got after compiling, can anyone please explain me how to rectify it?

Main.java:69: error: class, interface, or enum expected
public static void main (String[] args) throws java.lang.Exception
              ^
Main.java:72: error: class, interface, or enum expected
    Interval i1 = new Interval(1,3);
    ^
Main.java:73: error: class, interface, or enum expected
    Interval i2 = new Interval(2,6);
    ^
Main.java:74: error: class, interface, or enum expected
    Interval i3 = new Interval(8,10);
    ^
Main.java:75: error: class, interface, or enum expected
    Interval i4 = new Interval(15,18);
    ^
Main.java:77: error: class, interface, or enum expected
    x.add(i1);x.add(i2);x.add(i3);x.add(i4);
    ^
Main.java:77: error: class, interface, or enum expected
    x.add(i1);x.add(i2);x.add(i3);x.add(i4);
              ^
Main.java:77: error: class, interface, or enum expected
    x.add(i1);x.add(i2);x.add(i3);x.add(i4);
                        ^
Main.java:77: error: class, interface, or enum expected
    x.add(i1);x.add(i2);x.add(i3);x.add(i4);
                                  ^
Main.java:79: error: class, interface, or enum expected
        ArrayList<Interval> r = merge(x);
        ^
Main.java:81: error: class, interface, or enum expected
        for(Interval i : r)
        ^
Main.java:84: error: class, interface, or enum expected
        }
        ^
12 errors

Answer 1

Ideone.java:

import java.util.*;

public class Ideone
{   
    public static void main (String[] args) throws java.lang.Exception
    {
        ArrayList<Interval> x = new 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));

        x = merge(x);

        for(Interval i : x)
        {
            System.out.println(i.getStart() + " " + i.getEnd());
        }
    }

    public static ArrayList<Interval> merge(ArrayList<Interval> intervals) {

        if(intervals.size() == 0 || intervals.size() == 1)
            return intervals;

        Collections.sort(intervals, new IntervalComparator());

        Interval first = intervals.get(0);
        int start = first.getStart();
        int end = first.getEnd();

        ArrayList<Interval> result = new ArrayList<Interval>();

        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();
            }
        }

        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)
    {
        return i1.getStart() - i2.getStart();
    }
}

• main method is inside the public class Ideone
• Interval and IntervalComparator are just inner classes

Output:

1 6
8 10
15 20

Answer 2

Here is your refined code:

import java.util.*;
import java.lang.*;
import java.io.*;

class Interval {
    int start;
    int end;

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

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

public class Ideone {
    public static void main(String[] args) throws java.lang.Exception {
        ArrayList<Interval> x = new ArrayList<Interval>();
        Interval i1 = new Interval(1, 3);
        Interval i2 = new Interval(2, 6);
        Interval i3 = new Interval(8, 10);
        Interval i4 = new Interval(15, 18);

        x.add(i1);
        x.add(i2);
        x.add(i3);
        x.add(i4);

        ArrayList<Interval> r = merge(x);

        for (Interval i : r) {
            System.out.println(i.start + " " + i.end);
        }

    }

    public static ArrayList<Interval> merge(ArrayList<Interval> intervals) {

        if (intervals.size() == 0)
            return intervals;
        if (intervals.size() == 1)
            return intervals;

        Collections.sort(intervals, new IntervalComparator());

        Interval first = intervals.get(0);
        int start = first.start;
        int end = first.end;

        ArrayList<Interval> result = new ArrayList<Interval>();

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

        }

        result.add(new Interval(start, end));

        return result;

    }
}

class IntervalComparator implements Comparator {
    public int compare(Object o1, Object o2) {
        Interval i1 = (Interval) o1;
        Interval i2 = (Interval) o2;
        return i1.start - i2.start;
    }
}

And name this java file "Ideone.java"

Answer 3

My implementation using BST. O(logn) to merge: Inorder traversal gives you updated intervals.

private static Interval add(Interval root, Interval x){
    if(root == null)
        return x;
    if(root.start >= x.start){
        root.left = add(root.left,x);
        if(mergeLeft(root,root.left)){
            root.left = null;
        }               
    }
    else{
        root.right = add(root.right,x);
        if(mergeRight(root,root.right)){
            root.right = null;
        }
    }

    return root;
}

private static boolean mergeLeft(Interval root,Interval left){
    if(left.end < root.start)
        return false;

    else{
        root.start = Math.min(root.start, left.start);
        root.end = Math.max(root.end, left.end);
        return true;
    }
}

private static boolean mergeRight(Interval root,Interval right){
    if(right.start > root.end)
        return false;
    else{
        root.start = Math.min(root.start, right.start);
        root.end = Math.max(root.end, right.end);
        return true;
    }
}

Answer 4

I would rather put the merge method like this:

static List<Interval> merge(List<Interval> iList) {
    Collections.sort(iList, new Comparator<Interval>() {
        @Override
        public int compare(Interval o1, Interval o2) {
            return o1.startTime - o2.startTime;
        }
    });

    Interval prevIntvl = iList.get(0);
    List<Interval> res = new ArrayList<>();
    for (int i = 1; i < iList.size(); i++) {
        Interval curIntvl = iList.get(i);
        if (curIntvl.startTime < prevIntvl.endTime) {
            prevIntvl.setEndTime(prevIntvl.endTime > curIntvl.endTime ? prevIntvl.endTime : curIntvl.endTime);
        } else {
            res.add(prevIntvl);
            prevIntvl = curIntvl;
        }
    }

    res.add(prevIntvl);

    return res;
}

Answer 5

class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals.size() <= 1) {
            return intervals;
        }
        intervals.sort((i1, i2) -> Integer.compare(i1.start, i2.start));
        List<Interval> result = new LinkedList<Interval>();
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for(Interval interval : intervals) {
            if (interval.start <= end) {
                end = Math.max(end, interval.end);
            }
            else {
                result.add(new Interval(start, end));
                start = interval.start;
                end = interval.end;
            }
        }
        result.add(new Interval(start, end));
        return result;
    }
}