期間の計算

質問

SQLされたある開始日、終了日がｎ個あり、それらのトータルの期間の合計を求めます。単純に一つ一つの期間を出して全部足すのではなく、重なっている部分を取り除きたいのですが解法が見出せません。よろしくお願いします。西暦、月はそれぞれint形に変換しております。
　　例　　

n 　　開始日　　　終了日
　1 　2000/1　　　2005/2
　2 　2003/2　　　2004/8
　3 　2004/8　　　2005/5
4 2005/10 2005/12

　１の期間は５年１ケ月、２の期間は１年６ヵ月
３の期間は９ヶ月です。４の期間は２ヶ月重なっている期間や空白の期間を省くトータルの期間は５年６ヵ月となります。この５年６ヵ月を求めるアルゴリズムが思いつきません。よろしくお願いします。なおのｎはwhile(rs.next()){　}
でループしています。

回答No.1

takaP-

う～ん、多分これには定石みたいなのがあると思うんですよ。。。が！いかんせん無学な私はそれを知りません。
取り敢えず思い付いたやり方を書きますんで、それを土台に改良なりをしてみて下さい（それでも回答が無いよりはマシでしょうから・ｗ）

まずは、年と月をそれぞればらばらにして保持しているようですが、面倒なのでまとめてしまいましょう。
総月数　＝　年×１２＋月

例)
int n1_top = 2000 * 12 + 1 ;　//開始日
int n1_tail= 2005 * 12 + 2 ;　//終了日

次は、２重配列を作ります

例）
int[][] array={{n1_top,n1_tail},{n2_top,n2_tail}・・ {n*_top,n*_tail}};

次は、今作った２重配列をソートしてしまいます。
多重配列のソートに関しては丁度、最近ここの掲示板で話題がありましたので、それを参照して下さい。
http://www.okweb.ne.jp/kotaeru.php3?q=603859
ソートは n*_top（開始日）の値の比較で小さい順に並べ替えます。

次に、下記の処理を加えます。

例）

for(int i=0; i<array.length-1; i++){
　　if(array[i][1]>array[i+1][0]){
　　　　array[i+1][0]=array[i][1] ;
　　　　if(array[i][1]>array[i+1][1]){
　　　　　　array[i+1][1]=array[i][1];
　　　　}
　　}
}

やっている事は、前回の終了日と次回の開始日を比較し、もし、終了日よりも開始日が早ければ（日数が被っていれば）次回の開始日を「前回の終了日の値」へと変更すし、かつ、次回の終了日が前回の終了日よりも早ければ、同様に「前回の終了日の値」へと変更しています。
これにより、重複している部分は排除されるはずです。
そして、目的の「重なっている期間や空白の期間を省くトータルの期間」を求める時は、もう重複部分はありませんので

例）
int ans=0;
for(int i=0; i<array.length; i++){
　　ans+=array[i][1]-array[i][0];
}

とかする事で、期間が求まると思います（たぶんですが・汗
こればベストだとは『とても、とても』口が裂けても言えませんが、どうしても良案が思いつかないのでご勘弁を。

もう少し回答待ちをして、経験者の方のアドバイスを求めた方が良いでしょう。

お礼

takaさん回答ありがとうございます。二重配列を利用すると考えやすくなりますね。takaさんの回答をお手本に自分でも考えて見ます。ありがとうございました！