题目意思是有一堆按照start time排好序的time intervals，和一个单独的interval,判断是否这个interval是否可以插空
package google;
import java.util.*;
public class IntervalHasOverlap {
private static class Interval {
public int start;
public int end;
public Interval(int s, int e) {
start = s;
end = e;
}
@Override
public String toString() {
return "[start=" + start + ", end=" + end + "]";
}
}
private static boolean hasOverlap(Interval a, int beg, int end) {
if (end < a.start || beg > a.end) {
return false;
}
return true;
}
public static boolean hasOverlap(List<Interval> schedule, Interval target) {
if (schedule.isEmpty() || schedule == null) {
return false;
}
if (target.end < schedule.get(0).start) {
return false;
}
Interval last = schedule.get(0);
int curBeg = last.start;
for (int i = 1; i < schedule.size(); i++) {
Interval cur = schedule.get(i);
if (cur.start <= last.end) {
if (cur.end > last.end) {
last = cur;
}
} else {
// free interval: (last.end, cur.start)
if (last.end < target.start && target.end < cur.start) {
return false;
}
last = cur;
curBeg = cur.start;
}
if (hasOverlap(target, curBeg, last.end)) {
return true;
}
}
return false;
}
public static void main(String[] args) {
List<Interval> avails = new ArrayList<>();
avails.add(new Interval(10, 12));
avails.add(new Interval(10, 13));
avails.add(new Interval(14, 17));
avails.add(new Interval(20, 26));
avails.add(new Interval(20, 28));
// [10, 13], [14, 17], [20, 28]
for (Interval target : Arrays.asList(
new Interval(1, 14), new Interval(1, 8), new Interval(1, 10), new Interval(10, 17),
new Interval(13, 14), new Interval(17, 19), new Interval(18, 19), new Interval(19, 19),
new Interval(28, 28), new Interval(28, 30),
new Interval(29, 30), new Interval(1, 9))
) {
System.out.println(target + " " + hasOverlap(avails, target));
}
}
}