Menu
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
695
Merge Intervals. Given an array of intervals where intervals[i] = [starti, endi] , merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Let's take the following overlapping intervals example to explain the idea: If both ranges have at least one common point, then we say that they're overlapping. In other words, we say that two ranges and are overlapping if: On the other hand, non-overlapping ranges don't have any points in common.
Traverse all the set of intervals and check whether the consecutive intervals overlaps or not. If the intervals(say interval a & interval b) doesn't overlap then the set of pairs form by [a. end, b. start] is the non-overlapping interval.
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 classesOutput:
1 6
8 10
15 20
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"
41
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;
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
