두 개의 기간이 주어지면 두 기간이 중복되는지 여부를 결정하는 가장 간단하거나 효율적인 방법은 무엇입니까?
예를 들어, DateTime 변수로 표시되는 범위 StartDate1가 EndDate1 및 로 있다고 가정 StartDate2합니다 EndDate2.
답변
(StartA <= EndB) 및 (EndA> = StartB)
증명 :
조건 A가 DateRange A가 DateRange B 이후에 완전히 있음을 의미하도록 함
_ |---- DateRange A ------|
|---Date Range B -----| _
(참인 경우 StartA > EndB)
조건 B가 DateRange A가 DateRange B 이전에 완전 함을 의미 함
|---- DateRange A -----| _
_ |---Date Range B ----|
(참인 경우 EndA < StartB)
그러면 A 또는 B가 모두 참
이 아닌 경우 오버랩이 존재합니다.- 한 범위가 다른 범위를 완전히
따르지 않거나 다른 범위를 완전히 따르지 않으면 범위가 겹치게됩니다.
이제 De Morgan의 법률 중 하나는 다음과 같이 말합니다.
Not (A Or B) <=> Not A And Not B
다음과 같이 해석됩니다. (StartA <= EndB) and (EndA >= StartB)
참고 : 여기에는 가장자리가 정확히 겹치는 조건이 포함됩니다. 당신이를 제외하고자하는 경우,
변경 >=에 대한 연산자를 >, 그리고 <= 에<
노트 2. @Baodad 덕분에, 볼 이 블로그를 실제 중복의 이상입니다 :
{ endA-startA, endA - startB, endB-startA, endB - startB}
(StartA <= EndB) and (EndA >= StartB)
(StartA <= EndB) and (StartB <= EndA)
노트 3. @tomosius 덕분에 더 짧은 버전은 다음과 같이 읽습니다.
DateRangesOverlap = max(start1, start2) < min(end1, end2)
이것은 실제로 더 긴 구현에 대한 구문 바로 가기입니다. 여기에는 시작 날짜가 종료 날짜 또는 그 이전인지 확인하기위한 추가 검사가 포함됩니다. 위에서 이것을 파생 :
시작과 끝 날짜, 즉 위해, 밖으로 될 수 있다면, 가능성이있는 경우 startA > endA또는 startB > endB, 당신은 또한 순서에 있는지 확인해야합니다 그래서 당신이 두 개의 추가 유효성 규칙을 추가 할 필요가 수단 :
(StartA <= EndB) and (StartB <= EndA) and (StartA <= EndA) and (StartB <= EndB)
나 :
(StartA <= EndB) and (StartA <= EndA) and (StartB <= EndA) and (StartB <= EndB)
또는,
(StartA <= Min(EndA, EndB) and (StartB <= Min(EndA, EndB))
또는 :
(Max(StartA, StartB) <= Min(EndA, EndB)
그러나 구현 Min()하고 Max(), 당신은 (간결성을 위해 C의 원을 사용), 코드가, :
(StartA > StartB? Start A: StartB) <= (EndA < EndB? EndA: EndB)
답변
다음과 같은 경우 두 범위가 겹치는 것으로 충분하다고 생각합니다.
(StartDate1 <= EndDate2) and (StartDate2 <= EndDate1)
답변
이 문서의 .NET 용 기간 라이브러리 에서는 열거 형 PeriodRelation에 의한 두 기간의 관계에 대해 설명합니다 .
// ------------------------------------------------------------------------
public enum PeriodRelation
{
After,
StartTouching,
StartInside,
InsideStartTouching,
EnclosingStartTouching,
Enclosing,
EnclosingEndTouching,
ExactMatch,
Inside,
InsideEndTouching,
EndInside,
EndTouching,
Before,
} // enum PeriodRelation
답변
시간적 관계 (또는 다른 간격 관계에 대한 추론)에 대해서는 Allen의 간격 대수를 고려하십시오 . 두 구간이 서로에 대해 가질 수있는 13 가지 가능한 관계를 설명합니다. 다른 참조를 찾을 수 있습니다. “Allen Interval”은 실용적인 검색어 인 것 같습니다. 또한 이러한 작업에 대한 정보는 Snodgrass의 SQL에서 시간 지향적 응용 프로그램 개발 (PDF에서 온라인으로 제공), 날짜, Darwen 및 Lorentzos 시간 데이터 및 관계형 모델 (2002) 또는 시간 및 관계 이론 : 시간 데이터베이스 관계형 모델 및 SQL (2014; 사실상 TD & RM의 두 번째 버전).
짧은 (ish) 답변은 두 개의 날짜 간격 A과 B구성 요소 .start및 .end제약 조건이있는 .start <= .end경우 다음 과 같은 경우 두 간격이 겹칩니다.
A.end >= B.start AND A.start <= B.end
중첩 정도에 대한 요구 사항을 충족하도록 >=vs >및 <=vs 의 사용을 조정할 수 있습니다 <.
ErikE 의견 :
당신이 재미있는 것을 세면 13을 얻을 수있다. 현명한 계산으로, 나는 단지 6을 얻습니다. 그리고 당신이 A 또는 B가 먼저 오는 것을 돌보는다면, 나는 단지 3을 얻습니다 (교차하지 않고, 부분적으로 교차하고, 하나는 완전히 다른 것 안에 있습니다). 15는 다음과 같이 진행됩니다 : [이전 : 전, 시작, 내부, 종료, 후], [시작 : 시작, 내부, 종료, 후], [내 :: 내, 끝, 후], [종료 : 종료, 후], [ 이후 : 후].
나는 ‘before : before’와 ‘after : after’의 두 항목을 셀 수 없다고 생각합니다. 역수와의 관계를 동일시하면 7 개의 항목을 볼 수 있습니다 (참조 된 Wikipedia URL의 다이어그램 참조; 7 개의 항목이 있으며 그중 6 개는 다른 역수를 가지며 동일한 수의 역수는 없습니다). 그리고 세 가지가 합리적인지 여부는 요구 사항에 따라 다릅니다.
----------------------|-------A-------|----------------------
|----B1----|
|----B2----|
|----B3----|
|----------B4----------|
|----------------B5----------------|
|----B6----|
----------------------|-------A-------|----------------------
|------B7-------|
|----------B8-----------|
|----B9----|
|----B10-----|
|--------B11--------|
|----B12----|
|----B13----|
----------------------|-------A-------|----------------------
답변
오버랩 자체도 계산해야하는 경우 다음 공식을 사용할 수 있습니다.
overlap = max(0, min(EndDate1, EndDate2) - max(StartDate1, StartDate2))
if (overlap > 0) {
...
}
답변
범위가 서로 관련되어있는 위치를 기반으로 다양한 조건을 확인하는 모든 솔루션 은 특정 범위가 더 일찍 시작되도록함으로써 크게 단순화 될 수 있습니다 ! 필요한 경우 먼저 범위를 교체하여 첫 번째 범위가 더 빨리 (또는 동시에) 시작되는지 확인하십시오.
그런 다음 다른 범위 시작이 첫 번째 범위 끝보다 작거나 같은 경우 (범위가 포함 및 시작 시간과 종료 시간을 모두 포함하는 경우)보다 작거나 (범위가 시작 포함 및 종료를 제외한 범위 인 경우) 겹침을 감지 할 수 있습니다. .
양쪽 끝을 모두 포함한다고 가정하면 겹치지 않는 네 가지 가능성 만 있습니다.
|----------------------| range 1
|---> range 2 overlap
|---> range 2 overlap
|---> range 2 overlap
|---> range 2 no overlap
범위 2의 끝 점이 입력되지 않습니다. 따라서 의사 코드에서 :
def doesOverlap (r1, r2):
if r1.s > r2.s:
swap r1, r2
if r2.s > r1.e:
return false
return true
이것은 훨씬 더 단순화 될 수 있습니다 :
def doesOverlap (r1, r2):
if r1.s > r2.s:
swap r1, r2
return r2.s <= r1.e
범위가 끝에서 시작과 독점에 포함하는 경우, 당신은 교체해야 >와 >=두 번째에 if(: 두 번째 코드 세그먼트에, 당신은 사용하려는 첫 번째 코드 세그먼트에 대한 문 <이 아닌 <=) :
|----------------------| range 1
|---> range 2 overlap
|---> range 2 overlap
|---> range 2 no overlap
|---> range 2 no overlap
범위 1이 범위 2 이후에 시작되지 않도록하여 문제 공간의 절반을 조기에 제거하므로 확인 횟수를 크게 제한합니다.
답변
JavaScript를 사용하는 또 다른 솔루션이 있습니다. 내 솔루션의 전문 분야 :
- null 값을 무한대로 처리
- 하한을 포함하고 상한을 독점으로 가정합니다.
- 많은 테스트와 함께 제공
테스트는 정수를 기반으로하지만 JavaScript의 날짜 객체는 비교할 수 있으므로 두 개의 날짜 객체도 넣을 수 있습니다. 또는 밀리 초 타임 스탬프를 던질 수 있습니다.
암호:
/**
* Compares to comparable objects to find out whether they overlap.
* It is assumed that the interval is in the format [from,to) (read: from is inclusive, to is exclusive).
* A null value is interpreted as infinity
*/
function intervalsOverlap(from1, to1, from2, to2) {
return (to2 === null || from1 < to2) && (to1 === null || to1 > from2);
}테스트 :
describe('', function() {
function generateTest(firstRange, secondRange, expected) {
it(JSON.stringify(firstRange) + ' and ' + JSON.stringify(secondRange), function() {
expect(intervalsOverlap(firstRange[0], firstRange[1], secondRange[0], secondRange[1])).toBe(expected);
});
}
describe('no overlap (touching ends)', function() {
generateTest([10,20], [20,30], false);
generateTest([20,30], [10,20], false);
generateTest([10,20], [20,null], false);
generateTest([20,null], [10,20], false);
generateTest([null,20], [20,30], false);
generateTest([20,30], [null,20], false);
});
describe('do overlap (one end overlaps)', function() {
generateTest([10,20], [19,30], true);
generateTest([19,30], [10,20], true);
generateTest([10,20], [null,30], true);
generateTest([10,20], [19,null], true);
generateTest([null,30], [10,20], true);
generateTest([19,null], [10,20], true);
});
describe('do overlap (one range included in other range)', function() {
generateTest([10,40], [20,30], true);
generateTest([20,30], [10,40], true);
generateTest([10,40], [null,null], true);
generateTest([null,null], [10,40], true);
});
describe('do overlap (both ranges equal)', function() {
generateTest([10,20], [10,20], true);
generateTest([null,20], [null,20], true);
generateTest([10,null], [10,null], true);
generateTest([null,null], [null,null], true);
});
});karma & jasmine & PhantomJS로 실행 한 결과 :
PhantomJS 1.9.8 (Linux) : 20 개 중 20 개 성공 (0.003 초 /0.004 초)
