Determine if two given time ranges overlap
Given the following example:
0 2 4 6 8 10 12 14 16 18 20 22 24
Hour: |--|--|--|--|--|--|--|--|--|--|--|--|
A: ------| |---------
B: |-----------|
C: ---| |------------
D: |--------|
E: |-----|
A(from 18:00 to 04:00)
B(from 02:00 to 10:00)
C(from 16:00 to 02:00)
D(from 00:00 to 06:00)
E(from 20:00 to 00:00)
What is the most efficient way to determine if two given time ranges overlap?
Notice that if a time range is between 02:00 and 10:00 (B) it will overlap the time range from 18:00 and 04:00 (A) in the time between 02:00 and 04:00.
I'm trying to calculate this using TimeRange.getSecondOfDay() that return 0 if the hour is 00:00:00 and 86400 if the hour is 23:59:59. Every day start from 0.
In general case, for given A there are three regions of values of B, so one way or another, you have to check them all. Relatively easy way is to "shift" one range so that it starts at 00:00, like this:
bool Overlap(Range a, Range b){
time b_from = (b.from-a.from+86400)%86400;
time b_to = (b.to-a.from+86400)%86400;
time a_to = (a.to-a.from+86400)%86400;
return !(b_from<=b_to && b_from>=a_to);
}
First, you need to normalize your intervals: if an interval wraps to the next day, ie the end time is before the start time, add 24 hours to the end time.
Now your intervals will look like this:
A(from 18:00 to 28:00)
B(from 02:00 to 10:00)
C(from 16:00 to 26:00)
D(from 00:00 to 06:00)
E(from 20:00 to 00:00)
If you are working with TimeRange.getSecondOfDay() , you need to add corresponding number of seconds, ie 24*60*60*60
Once the intervals are normalized, you can use the usual formula for determining the overlap:
int overlap = MIN(a.end, b.end) - MAX(a.begin, b.begin);
if (overlap > 0) {
...
}
上一篇: 枚举和匹配属性的C＃命名约定
下一篇: 确定两个给定的时间范围是否重叠