令人惊讶的是许多ans WERS在很短的时间...
我跟着一个已经在其他的答案提出了同样的想法:当启动时间s
比结束时间e
较小,那么结果可以分解为两个独立的计算,范围为[s,24]
和[0,e]
。
这可以“互相”完成,因此只有3个简单的情况需要考虑,剩下的可以通过递归调用完成。
不过,我试图
- 考虑的是,(根据图像),结束点应包容(!)
- 添加一些多个测试用例
- 可视化的结构很好地:-)
这是其结果作为MCVE:
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));
}
}
前两个测试用例是具有的那些已在问题中给出,并分别正确地打印12
和4
。剩下的两个被用于测试其他重叠配置:
......AAAAAAAAAAAAAAAAAA
..BBBBBBBBBBBBBBBB......
12
AAAAAAAAAAAAA...........
BBB.........BBBBBBBBBBBB
4
AAAAA......AAAAAAAAAAAAA
BBBB........BBBBBBBBBBBB
16
AAAAA.......AAAAAAAAAAAA
BBBB.......BBBBBBBBBBBBB
16
然而,请注意,进一步的测试配置可以具有以覆盖所有可能的情况下被创建。
在第二个示例中,该间隔是如何破坏的?你会如何在startTime和endTime中表示它? –
@RahulJain'startTime = 12','endTime = 2'。这是一个循环的世界。 – Daniel
我一直在为你发布代码,但StackOverflow一直警告我,缩进不正确 –