PHPz2017-04-18 09:34:05
새로운 창작물을 생성할 때마다 현재 생성된 세트와 중복되는 세트를 먼저 찾아낸 후 중복되는 세트 쌍이 있는지 확인해야 합니다. 이렇게 하면 동일한 세트에 세트가 생성되지 않습니다.
ringa_lee2017-04-18 09:34:05
삽입 시 테이블을 순회하여 현재 타임스탬프가 두 타임스탬프 사이에 있는지 확인하고 이 조건을 충족하는 숫자를 기록합니다. >= 3이면 삽입이 수행되지 않습니다. 그렇지 않으면 데이터 테이블에 삽입하십시오.
阿神2017-04-18 09:34:05
전형적인 라인 세그먼트 커버리지 문제. 저는 Java를 모르므로 O(n) 아이디어를 알려 드리겠습니다.
먼저 검증할 구간과 교차하는 구간을 모두 찾아 구간의 왼쪽 끝점을 기준으로 작은 것부터 큰 것 순으로 정렬
첫 번째 간격을 CurrentInternal로 기억
CurrentInternal의 경우 다음 항목 NextInterval을 검사합니다. CurrentInternal과 교차하지 않으면 이를 CurrentInternal로 기록하고 2로 점프하고 그렇지 않으면 교차 간격을 Intersection으로 기록합니다.
Intersection의 경우 NextInterval 이후 항목을 순회합니다. Intersection과 교차하는 간격이 없으면 NextInterval을 CurrentInterval로 기록하고 2로 점프합니다. 그렇지 않으면 세 개의 교차 간격이 있고 종료됩니다.
전체 목록을 순회하면 검증할 간격이 적법하다는 것을 증명합니다.
https://jsfiddle.net/hsfzxjy/7td0rwr2/28/