更新时间:2023-01-29 21:01:06
这是O(nlog(n)),或者显然如果有很多碰撞,它是O(碰撞次数)。一个我曾经工作的公司使用类似于这个面试问题的东西。
Here's O(nlog(n)), or obviously if there are lots of collisions, it's O(number of collisions). A company I used to work for used something similar to this as an interview question.
private static class BookingTuple implements Comparable<BookingTuple> {
public final Date date;
public final boolean isStart;
public final int id;
public BookingTuple(Date date, boolean isStart, int id) {
this.date = date;
this.isStart = isStart;
this.id = id;
}
@Override
public int compareTo(BookingTuple other) {
int dateCompare = date.compareTo(other.date);
if (dateCompare != 0) {
return dateCompare;
} else {
if (!isStart && other.isStart) {
return -1;
} else if (isStart && !other.isStart) {
return 1;
} else {
return 0;
}
}
}
}
public static boolean isOverlappingDates(List<BookingDateRange> dateRangeList, List<String> overlappingDatePairs) {
List<BookingTuple> list = new ArrayList<BookingTuple>();
for (int i = 0; i < dateRangeList.size(); i++) {
Date from = dateRangeList.get(i).getFromDate();
Date to = dateRangeList.get(i).getToDate();
list.add(new BookingTuple(from, true, i));
list.add(new BookingTuple(to, false, i));
}
Collections.sort(list);
boolean overlap = false;
HashSet<Integer> active = new HashSet<Integer>();
for (BookingTuple tuple : list) {
if (!tuple.isStart) {
active.remove(tuple.id);
} else {
for (Integer n : active) {
overlappingDatePairs.add(n + "_" + tuple.id);
overlap = true;
}
active.add(tuple.id);
}
}
return overlap;
}