私は例えば、2時間の範囲の間のオーバーラップする時間数を見つけるためのアルゴリズムを把握しようとしてきた：アルゴリズム - 巡回世界でオーバーラップ間隔（24時間）の期間を探す
は12
そして
を返す必要があります。
だから、私は次の関数を作成する際にギャップを埋める助けてください：
public static Long findOverlappingInterval(Long startTime1, Long endTime1,
Long startTime2, Long endTime2){
// Any suggestions?
}
感謝。
EDIT： ANDを使用して2つのバイナリ配列を作成し、その結果を合計する方法を知っています。 意味：
しかし、私はSolrのクエリのためのアルゴリズムのアイデアを使用したいので、それは私の特定のニーズを助けないだろう、そうは、アレイおよび二項演算子を使用すると、私ためのオプションではありません。
驚くほど多くのans私はすでに他の回答で提案されたのと同じ考え方続く
短時間でwers ...：開始時刻s終了時刻eよりも小さい場合には、その結果を2つの別々の計算に分けることができますが、範囲は[s,24]と[0,e]です。
これは「相互に」行うことができるため、考慮する必要があるのは3つの単純なケースだけであり、残りのものは再帰呼び出しで行うことができます。
しかし、私は
（画像による）、エンドポイントは（ 包括べきであるという事実を考えるpublic class OverlappingIntervals
{
private static final long INTERVAL_SIZE = 24;
public static void main(String[] args)
{
test(6,23, 2,17);
test(0,12, 12,2);
test(11,4, 12,3);
test(12,4, 11,3);
}
private static void test(
long s0, long e0, long s1, long e1)
{
System.out.println(createString(s0, e0, s1, e1));
System.out.println(findOverlappingInterval(s0, e0, s1, e1));
}
private static String createString(
long s0, long e0, long s1, long e1)
{
StringBuilder sb = new StringBuilder();
sb.append(createString(s0, e0, "A")).append("\n");
sb.append(createString(s1, e1, "B"));
return sb.toString();
}
private static String createString(long s, long e, String c)
{
StringBuilder sb = new StringBuilder();
for (int i=0; i<INTERVAL_SIZE; i++)
{
if (s < e)
{
if (i >= s && i <= e)
{
sb.append(c);
}
else
{
sb.append(".");
}
}
else
{
if (i <= e || i >= s)
{
sb.append(c);
}
else
{
sb.append(".");
}
}
}
return sb.toString();
}
public static long findOverlappingInterval(
long s0, long e0, long s1, long e1)
{
return compute(s0, e0+1, s1, e1+1);
}
public static long compute(
long s0, long e0, long s1, long e1)
{
if (s0 > e0)
{
return
compute(s0, INTERVAL_SIZE, s1, e1) +
compute(0, e0, s1, e1);
}
if (s1 > e1)
{
return
compute(s0, e0, s1, INTERVAL_SIZE) +
compute(s0, e0, 0, e1);
}
return Math.max(0, Math.min(e0, e1) - Math.max(s0, s1));
}
}
最初の2つのテストケースを持っているものです。）
:-)うまく構成を可視化するいくつかのより多くのテストケースを追加します。その質問には、それぞれ12と4が正しく印刷されています。残りの二つは、他の重複設定をテストするために意図されている：
......AAAAAAAAAAAAAAAAAA
..BBBBBBBBBBBBBBBB......
12
AAAAAAAAAAAAA...........
BBB.........BBBBBBBBBBBB
4
AAAAA......AAAAAAAAAAAAA
BBBB........BBBBBBBBBBBB
16
AAAAA.......AAAAAAAAAAAA
BBBB.......BBBBBBBBBBBBB
16
しかしながら、さらなるテスト構成は、すべての可能なケースをカバーするために作成しなければならないかもしれないことに注意してください。
/** Start times must be smaller than end times */
public static int findOverlappingInterval(int startTime1, int endTime1, int startTime2, int endTime2) {
int overlappingTime = 0;
int[] time1 = new int[Math.abs(endTime1 - startTime1)];
for (int i1 = startTime1; i1 < endTime1; i1++) {
time1[i1 - startTime1] = i1;
}
int[] time2 = new int[Math.abs(endTime2 - startTime2)];
for (int i2 = startTime2; i2 < endTime2; i2++) {
time2[i2 - startTime2] = i2;
}
for (int i = 0; i < time1.length; i++) {
for (int j = 0; j < time2.length; j++) {
if (time1[i] == time2[j]) {
overlappingTime++;
}
}
}
return overlappingTime;
}
このメソッドは、必要な機能を果たすはずです。それは私のために働いた。 でもラッピングパーツは分かりません。この新しいコードは、あなたが望む何をすべき
EDIT
/** Returns the overlap between the four time variables */
public static int findOverlappingInterval(int startTime1, int endTime1, int startTime2, int endTime2) {
int overlappingTime = 0;
// First time
int time1Length = 0;
if (endTime1 < startTime1) {
time1Length = 24 - startTime1;
time1Length += endTime1;
}
int[] time1;
if (time1Length == 0) {
time1 = new int[Math.abs(endTime1 - startTime1)];
for (int i1 = startTime1; i1 < endTime1; i1++) {
time1[i1 - startTime1] = i1;
}
} else {
time1 = new int[time1Length];
int count = 0;
for (int i1 = 0; i1 < endTime1; i1++) {
time1[count] = i1;
count++;
}
for (int i1 = startTime1; i1 < 24; i1++) {
time1[count] = i1;
count++;
}
}
// Second time
int time2Length = 0;
if (endTime2 < startTime2) {
time2Length = 24 - startTime2;
time2Length += endTime2;
}
int[] time2;
if (time2Length == 0) {
time2 = new int[Math.abs(endTime2 - startTime2)];
for (int i2 = startTime2; i2 < endTime2; i2++) {
time2[i2 - startTime2] = i2;
}
} else {
time2 = new int[time2Length];
int count = 0;
for (int i2 = 0; i2 < endTime2; i2++) {
time2[count] = i2;
count++;
}
for (int i2 = startTime2; i2 < 24; i2++) {
time2[count] = i2;
count++;
}
}
// Overlap calculator
for (int i = 0; i < time1.length; i++) {
for (int j = 0; j < time2.length; j++) {
if (time1[i] == time2[j]) {
overlappingTime++;
}
}
}
return overlappingTime;
}
。それは24時間の周りにループします。
開始時間は終了時間*/'前提よりも小さくする必要がありません。 2番目の例では 'startTime'は' endTime'よりも大きいです。 – Daniel
私は今それにループを追加しました。 –
それは非効率的に見えます、それほど素朴な解決策が存在するはずです – AdamSkywalker
まず、間隔(a, b)(a > b)のために、我々は簡単に2つの間隔
(a , 23) and (0, b)
だから、
にそれを破ることができる、問題はそうa <= b and a1 <= b1
で(a , b)と(a1, b1)間の重複を見つけることになり、4つありますケース：
b < a1または重複がないことを意味、、、(a, b)は(a1, b1)を含むことを意味する0a <= a1 && b1 <= bは、(a1, b1)は(a, b)を含むことを意味b1 - a1 + 1a1 <= a && b <= b1を戻す戻り戻りb - a + 1(a, b)それぞれの(a1, b1)重なる部分でありますその重複間隔は、(max(a1, a), min(b, b1))です。配列を作成することなく、計算だけでインターバル間の交点。 3つのケースがあります。
分割された間隔の問題は、2つの別々の間隔として解決できます。再帰を使用して、簡単にこれを行うことができます：
public static Long findOverlappingInterval(Long startTime1, Long endTime1, Long startTime2, Long endTime2)
{
if (startTime1 < endTime1 && startTime2 < endTime2)
return Math.max(0, Math.min(endTime2, endTime1) - Math.max(startTime1, startTime2) + 1);
else
{
if (startTime1 < endTime1)
return findOverlappingInterval(startTime1, endTime1, 0L, endTime2) +
findOverlappingInterval(startTime1, endTime1, startTime2, 23L);
else if (startTime2 < endTime2)
return findOverlappingInterval(0L, endTime1, startTime2, endTime2) +
findOverlappingInterval(startTime1, 23L, startTime2, endTime2);
else
{
return findOverlappingInterval(0L, endTime1, 0L, endTime2) +
findOverlappingInterval(0L, endTime1, startTime2, 23L) +
findOverlappingInterval(startTime1, 23L, 0L, endTime2) +
findOverlappingInterval(startTime1, 23L, startTime2, 23L);
}
}
}
私は、両方の間隔が分割されているケースを明示的に扱う必要はないと考えています。最初のケースを再帰呼び出しで処理すると、最終的なelseの場合は決して到着しません。それにもかかわらず、明確な説明と（作業効率のよい）解決策のために+1。 – Marco13
チェックここでは、このリンク：Ideone link
をEDIT：
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static Long min(Long a,Long b){
return ((a)<(b)?(a):(b));
}
public static Long max(Long a,Long b){
return ((a)>(b)?(a):(b));
}
public static void main (String[] args) throws java.lang.Exception
{
Long s1=6L,e1=23L,s2=2L,e2=17L,ans=0L;
Boolean broken1,broken2;
broken1=(s1<=e1)?false:true;
broken2=(s2<=e2)?false:true;
if(broken1){
if(broken2)
ans=min(e1,e2)+1 + 23-max(s1,s2)+1;
else{
if(e1>=s2) ans+=(min(e1,e2)-s2+1);
if(s1<=e2) ans+=(e2-max(s1,s2)+1);
}
}
else{
if(broken2){
if(e2>=s1) ans+=(min(e1,e2)-s1+1);
if(s2<=e1) ans+=(e1-max(s1,s2)+1);
}
else{
if(e1<s2 || e2<s1) ans=0L;
else ans=min(e1,e2)-max(s1,s2)+1;
}
}
System.out.println(ans+"");
}
}
2番目の例では、どのように壊れた間隔ですか？あなたはstartTimeとendTimeでそれをどのように表現しますか？ –
@RahulJain 'startTime = 12'、' endTime = 2'です。それは周期的な世界です。 – Daniel
私はあなたのためにコードを投稿しようとしていますが、StackOverflowはインデントが正しくないことを警告し続けます。 –