假設計算集如下所示:
…[an，bn]∩[an+1，bn+1]∩[an+2，bn+2]∩…
標記為z
現在添加另壹個區間[c，d]
1.判斷是否c∈Z，然後判斷d，如果d不屬於Z，那麽我們去掉[c，d]之間包含的所有區間，將包含c的區間的右端點修改為d；如果D屬於Z，那麽我們把包含C和D的區間以及它們之間的區間合並成壹個區間。
2.如果c不屬於z，那麽將[c，d]加到z上，… [am，am+1] ∪ [c，d] ∪ [am+2，am+3] …，然後從區間[c，d]開始遍歷，去掉重復部分。
3.遍歷集合z的方法是從區間的左端開始，
代碼如下:* * * *兩個類:UnionAlgorithm.java和Interval.java。
包裝測試；
導入Java . util . ArrayList；
導入Java . util . arrays；
導入Java . util . list；
/**
* & ltpre & gt
*這個類使用ArrayList來表示區間的集合，每個元素表示壹個區間。
* ArrayList中元素的順序是指這些元素所代表的區間在數軸上按順序排列。
*
*
* & lt/pre & gt；
* @作者羅賢
* @自2008年9月5日下午4:38:09
* @版本1.0
*/
公共類UnionAlgorithm {
/**
*存儲結果集
*/
私有列表值= new ArrayList()；
/**
*計算主要方法
*
* @param param
* @返回
*/
公共列表計算(間隔[]參數){
interval[]interval = check(param)；
if(間隔== null ||間隔.長度== 0)
返回null
if(value . size()= = 0 & amp；& ampinterval.length & gt= 1)
value . add(interval[0])；
for(int I = 1；我& lt間隔.長度；i++) {
//確定值中區間左端點的位置。
int[]left _ position = get position(value，0，interval[i])。get left())；
if (left_position[0] == 1) {
//1左端點屬於值。
int[]right _ position = get position(value，left_position[1]，interval[i]。getRight())；
if(right _ position[0]= = 1){
//1.1右端點也屬於值。
if(left _ position[1]= = right _ position[1])
繼續；
((Interval)value . get(left _ position[1]))。setRight(
((Interval)value . get(right _ position[1]))。getRight())；
for(int j = left _ position[1]+1；j & lt= right _ position[1]；j++) {
value . remove(j)；
}
}否則{
//1.2右端點不屬於值。
((Interval)value . get(left _ position[1]))。setRight(interval[i].getRight())；
for(int j = left _ position[1]+1；j & ltright _ position[1]；j++) {
value . remove(j)；
}
}
}否則{
//2左端點不屬於value。
value . add(left _ position[1]，interval[I])；
刷新(left _ position[1])；
}
}
返回值；
}
公共void刷新(int index) {
Interval temp =(區間)value . get(index)；
int[]index _ right _ position = get position(value，index + 1，temp . getright())；
if(index _ right _ position[0]= = 1){
區間include_right =(區間)value . get(index _ right _ position[1])；
temp . setright(include _ right . getright())；
for(int I = index+1；我& lt= index _ right _ position[1]；i++) {
value . remove(I)；
}
} else if(index _ right _ position[0]= = 0){
//刪除此區間內的所有區間。
for(int I = index+1；我& ltindex _ right _ position[1]；i++) {
value . remove(I)；
}
}
}
/**
* & ltpre & gt
*在設定值中找到該點的位置。
*從序列號開始搜索。
*
* return:壹個數組，包含兩個值[type，index]。
*如果type=0，則表示該點不在設定值的任何區間內，在指標區間的前面。
*如果type=1，則表示該點在設定值中索引的元素區間內。
*
*(註:0型的特例是點在集合中最後壹個區間之後，此時，
*雖然value.get(value.size())不存在，我們還是把索引賦給value.size())。
*
* & lt/pre & gt；
* @param值
* @param來自
* @參數點
* @返回
*/
public int[] getPosition(列表值，int from，int point) {
if(from & gt；= value.size())
返回new int[]{0，value . size()}；
if(點& lt((Interval)value.get(from))。getLeft()) {
返回new int[]{0，from}。
}
for(int I = from；我& ltvalue . size()-1；i++) {
Interval tmp =(Interval)value . get(I)；
if (tmp.isContain(point))
return new int[]{1，I }；
Interval TM plater =(Interval)value . get(I+1)；
if(點& gttmp . getright()& amp；& amp點& lttmpLater.getLeft())
返回new int[]{0，I+1 }；
}
//比較最後壹個間隔
Interval last =(Interval)value . get(value . size()-1)；
if (last.isContain(point))
返回new int[]{1，value . size()-1 }；
其他
返回new int[]{0，value . size()}；
}
/**
*數組檢查時，數組右邊的元素數量不得少於右邊的元素。
* @param duan
* @返回
*/
公共間隔[]檢查(間隔[]臨時){
//:-不要破壞參數原則
Interval[] interval =新間隔[temp . length]；
for(int I = 0；我& lt間隔.長度；i++) {
interval[i] =新間隔(temp[I])；
}
//:-
int長度= interval.length
for(int I = 0；我& lt間隔.長度；i++) {
if(區間[i]。getRight()& lt；區間[i]。getLeft()) {
區間[i] =空；
長度-；
}
}
Interval[] result =新的間隔[length]；
int index = 0；
for(int I = 0；我& lt間隔.長度；i++) {
if (interval[i]！= null){
結果[索引] =區間[I]；
index++；
}
}
返回結果；
}
公共列表getValue() {
返回值；
}
公共靜態void main(String[] args) {
Interval[]v = {新區間(1，3)，新區間(4，2)}；
union algorithm ua = new union algorithm()；
區間d1 =新區間(7，9)；
區間d2 =新區間(5，7)；
區間d3 =新區間(-1，4)；
區間d4 =新區間(8，10)；
區間d5 =新區間(10，12)；
區間d6 =新區間(4，1)；
區間d7 =新區間(8，10)；
區間d8 =新區間(3，14)；
區間d9 =新區間(15，17)；
區間c1 =新區間(0，4545)；
區間c2 =新區間(32，54)；
區間c3 =新區間(123456)；
區間c4 =新區間(34，54)；
區間c5 =新區間(12，23)；
區間[]段= {d1，d2，D3 }；
// Interval[] duan = {d1，d2，d3，d4，d5，，d7，d8，d9，c1，c2，c3，c4，C5 }；
long sc = system . current time millis()；
ua.calc(段)；
//thread . sleep(1)；
sc = system . current time millis()-sc；
系統。out . println(ua . getvalue()+" Cost:"+sc)；
}
}
//下面是間隔bean。
包裝測試；
/**
*表示間隔[左，右]
* @作者羅賢
* @自2008年9月5日下午4:48:15
* @版本1.0
*/
公共類間隔{
private int left
私有int權；
公共間隔(Interval interval) {
this . left = interval . get left()；
this . right = interval . getright()；
}
公共區間(int left，int right) {
this.left = left
this.right = right
}
public boolean is contain(int point){
if(點& lt=右& amp& amp點& gt=左)
返回true
其他
返回false
}
public int getLeft() {
向左返回；
}
public int getRight() {
向右返回；
}
public void setLeft(int left) {
this.left = left
}
public void setRight(int right) {
this.right = right
}
公共字符串toString(){
返回“[" +左+"，"+右+"]”；
}
}