import java.util.*;
class Range {
int begin;
int end;
Range(int begin, int end){
this.begin = begin;
this.end = end;
}
public static void main(String[] args) {
Range[] ranges = {
new Range(1,5),
new Range(2,4),
new Range(3,5),
new Range(5,9),
new Range(6,8),
new Range(8,10)
};
LinkedList<Range> uncrossedSections = qujian(ranges);
System.out.println("找到如下不相交的区间:");
for (int i = 0; i < uncrossedSections.size(); ++i) {
System.out.println("(" + uncrossedSections.get(i).begin + "," + uncrossedSections.get(i).end + ")");
}
}
public static LinkedList<Range> qujian(Range[] ranges){
LinkedList<Range> range = new LinkedList<>();
Arrays.sort(ranges, new Comparator<Range>() {
public int compare(Range left, Range right) {
if (left.end < right.end){
return -1;
}
else if (left.end == right.end) {
return 0;
}
else {
return 1;
}
}
});
LinkedList<Range> uncrossSections = new LinkedList<>();
uncrossSections.add(ranges[0]);
for(int i = 0; i < ranges.length; i++){
Range last = uncrossSections.getLast();
if(last.end <= ranges[i].begin){
uncrossSections.add(ranges[i]);
}
}
return uncrossSections;
}
}