重複の可能性：
間隔の
和集合間隔を効率的にオーバーラップする方法
間隔のリストがすべての整数であるとすると、それらが交差またはオーバーラップする場合は1つの間隔に折りたたむことができるはずです。そうでない場合、指定された間隔は影響を受けません。たとえば、入力がegI [（2-6）、（1-4）、（8-12）]の場合、期待される出力は[（1-6）、（8-12）]、たとえばII [（4- 7）、（2-6）、（1-4）、（8-12）、（7-9）]期待される出力は[（1-12）]です。
訂正：ソート部分が欠落しているため、はい、O（n）ではなくO（nlogn）時間です。それを指摘してくれてありがとう。私は、O（nlogn）時間とO（2n）空間アルゴリズムのアプローチを作成してテストしました。このアプローチのコードを以下で共有します。私は、この問題を解決するためのさまざまなアプローチ、おそらくより効率的な方法を聞くことに興味があります。
//各間隔（2〜6）などが「間隔」オブジェクト（以下に示すクラス定義）として表されると仮定します。ここで、low=2およびhigh=6 //ステップ1：指定された下限エンドポイントで並べ替えます区間//ステップ2：ソートされた区間のユニオンを見つける
//入力：
List<Interval> intervalList = new ArrayList<Interval>();
//出力：
List<Interval> unionList = new ArrayList<Interval>();
private static final Comparator<Interval> Low_EPSorter = new LowEPSorter();
class Interval {
int low, high;
Interval(int l, int h, int m) {
low = l;
high = h;
}
}
//// ------- BEGIN：指定された間隔のユニオンを見つけるメソッド---- //////
void UnionOfIntervals() {
//Find intersection and combine intervals as necessary
int sz = intervalList.size();
// sort by low endpoint
Collections.sort(intervalList, Low_EPSorter);
for(int i = 0; i < sz; i++) {
int j = i;
if(j > 0) {
if( Intervals.intersect(intervalList.get(j), intervalList.get(j-1)) ) {
Interval v = union(intervalList.get(j), intervalList.get(j-1));
checkAndAdd(v, unionList);
}
else {
if(i == 1) {
unionList.add(intervalList.get(j-1));
unionList.add(intervalList.get(j));
}
else {
unionList.add(intervalList.get(j));
}
} //No intersection
} //If 2 elements atleast
}
//Print intervals after union
System.out.println("Input intervals after sorting:");
for(Interval v : intervalList) {
System.out.print(v.low + "," + v.high + " ");
}
System.out.println();
System.out.println("Union of intervals:");
for(Interval v : unionList) {
System.out.print(v.low + "," + v.high + " ");
}
}
void checkAndAdd(Interval x, List t) {
int top = t.size()-1;
if( top >=0 && Intervals.intersect(unionList.get(top), x) ) {
Interval v = union(unionList.get(top), x);
t.remove(top);
t.add(v);
}
else {
t.add(x);
}
}
//// ------- END：指定された間隔のユニオンを見つけるメソッド---- //////
////---ヘルパーメソッド---////
static boolean intersect(Interval a, Interval b) {
boolean r = false;
if(b.high < a.low || b.low > a.high)
r = false;
else if(a.low <= b.high && b.low <= a.high)
r = true;
return r;
}
Interval union(Interval a, Interval b) {
int l = (a.low < b.low) ? a.low : b.low;
int max = (a.high > b.high) ? a.high : b.high;
return new Interval(l, max);
}
private static class LowEPSorter implements Comparator<Interval> {
public int compare(Interval a, Interval b) {
int r = 0;
if(a.low < b.low)
r = -1;
else if(a.low > b.low)
r = 1;
return r;
}
}