Überlappungsintervalle zusammenführen

Question

Frage: Gegeben einer Reihe von Zeitintervallen in beliebiger Reihenfolge, füge alle überlappenden Intervalle zu einem zusammen und gebe das Ergebnis aus, das nur sich gegenseitig ausschließende Intervalle haben sollte. Lassen Sie die Intervalle der Einfachheit halber als Ganzzahlpaare dargestellt werden. Zum Beispiel sei die gegebene Menge von Intervallen {{1,3}, {2,4}, {5,7}, {6,8}}. Die Intervalle {1,3} und {2,4} überlappen sich miteinander, so dass sie zusammengeführt werden sollten und {1, 4} werden. Ähnlich sollten {5, 7} und {6, 8} zusammengeführt werden und {5, 8} werden

Schreiben Sie eine Funktion, die die Menge der zusammengefügten Intervalle für die gegebene Menge von Intervallen erzeugt.

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

} 
} 

Dies sind die Fehler, die ich nach dem Kompilieren bekam, kann mir jemand bitte erklären, wie es zu korrigieren?

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 Methode ist ich nside die public class Ideone
• Interval und IntervalComparator sind nur innere Klassen

Ausgang:

1 6 
8 10 
15 20 

Answer 2

Hier ist Ihr verfeinerte 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; 
    } 
} 

Und der Name dieses Java-Datei "Ideone.java"

Answer 3

würde ich eher das Merge-Methode so:

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 4

Meine Implementierung mit BST. O (logn) zum Zusammenführen: Inorder traversal gibt Ihnen aktualisierte Intervalle.

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