如何检查循环范围的重叠（年度循环周期重叠）

Question

如何检查循环范围的重叠（年度循环周期重叠）

pythonrangecycleoverlap

4

我正在寻找一种优雅的算法来检查两个每年重复的时间段是否重叠。该时间段与年份无关，但可以预期每年都是闰年。

例如，时间段A =（3月1日至5月1日），时间段B =（4月1日至9月1日）重叠。同样，时间段A =（10月1日至2月1日）和时间段B =（1月1日至3月1日）也会重叠。

然而，我发现这比我预想的要困难得多。复杂性来自跨越年末的时间段。

我有一个可行的解决方案（请参见下面的 doesOverlap（A，B）方法），但我发现它很复杂。

# for the rest of the MWE context code, see further
# WORKING, but a bit convulted
def doesOverlap(A, B):  
    '''returns True if yearly period A and B have overlapping dates'''
    # list to track if day in year is part of a period A
    # (this could probably be done a bit cheaper with a dictionary of tuples, but not relevant for my question)
    yeardayCovered = [False for x in range(366)]  # leap year

    # mark the days of A
    for d in range(A.start, A.start + A.length):
        yeardayCovered[d % 366] = True

    # now check each of the days in B with A
    for d in range(B.start, B.start + B.length):
        if yeardayCovered[d % 366]:
            return True
    return False

我相信可以通过少量的检查和更加优雅的方式来实现。我尝试将开始时间中的一个设置为零偏移量，应用一些模运算，然后执行常规（非循环）范围重叠检查(算法检测重叠期间)，但我并没有让所有的测试案例都正常工作。

#NOT WORKING CORRECTLY!!
def doesOverlap(A, B):   
    '''determines if two yearly periods have overlapping dates'''
    Astart = A.start
    Astop = A.stop
    Bstart = B.start
    Bstop = B.stop

    # start day counting at Astart, at 0
    offset = Astart
    Astart = 0
    Astop = (Astop - offset) % 366
    Bstart = (Bstart - offset) % 366
    Bstop = (Bstop - offset) % 366

    # overlap?
    # https://dev59.com/2mYr5IYBdhLWcg3wpLr9#13513973
    return (Astart <= Bstop and Bstart <= Astop)

注意：我已经用Python编写了代码，但理想情况下解决方案不应太依赖于Python（即不使用通常只在Python中提供的函数，而不是在C或C#中）。

# MWE (Minimal Working Example)

import datetime
import unittest


class TimePeriod:
    def __init__(self, startDay, startMonth, stopDay, stopMonth):
        self.startDay = startDay
        self.startMonth = startMonth
        self.stopDay = stopDay
        self.stopMonth = stopMonth

    def __repr__(self):
        return "From " + str(self.startDay) + "/" + str(self.startMonth) + " to " + \
            str(self.stopDay) + "/" + str(self.stopMonth)

    def _dayOfYear(self, d, m, y=2012):
        '''2012 = leap year'''
        date1 = datetime.date(year=y, day=d, month=m)
        return date1.timetuple().tm_yday

    @property
    def start(self):
        '''day of year of start of period, zero-based for easier modulo operations! '''
        return self._dayOfYear(self.startDay, self.startMonth) - 1

    @property
    def stop(self):
        '''day of year of stop of period, zero-based for easier modulo operations! '''
        return self._dayOfYear(self.stopDay, self.stopMonth) - 1

    @property
    def length(self):
        '''number of days in the time period'''
        _length = (self.stop - self.start) % 366 + 1
        return _length

def doesOverlap(A, B):
    # code from above goes here


class TestPeriods(unittest.TestCase):
    pass


def test_generator(a, b, c):
    def test(self):
        self.assertEqual(doesOverlap(a, b), c)
    return test

if __name__ == '__main__':

    #some unit tests, probably not complete coverage of all edge cases though
    tests = [["max", TimePeriod(1, 1, 31, 12), TimePeriod(1, 1, 1, 1), True],
             ["BinA", TimePeriod(1, 3, 1, 11), TimePeriod(1, 5, 1, 10), True],
             ["BoverEndA", TimePeriod(1, 1, 1, 2), TimePeriod(10, 1, 3, 3), True],
             ["BafterA", TimePeriod(1, 1, 1, 2), TimePeriod(2, 2, 3, 3), False],
             ["sBoutA", TimePeriod(1, 12, 2, 5), TimePeriod(1, 6, 1, 7), False],
             ["sBoverBeginA", TimePeriod(1, 11, 2, 5), TimePeriod(1, 10, 1, 12), True],
             ["sBinA", TimePeriod(1, 11, 2, 5), TimePeriod(1, 1, 1, 2), True],
             ["sBinA2", TimePeriod(1, 11, 2, 5), TimePeriod(1, 12, 10, 12), True],
             ["sBinA3", TimePeriod(1, 11, 2, 5), TimePeriod(1, 12, 1, 2), True],
             ["sBoverBeginA", TimePeriod(1, 11, 2, 5), TimePeriod(1, 10, 1, 12), True],
             ["Leap", TimePeriod(29, 2, 1, 4), TimePeriod(1, 10, 1, 12), False],
             ["BtouchEndA", TimePeriod(1, 2, 1, 2), TimePeriod(1, 2, 1, 3), True]]

    for i, t in enumerate(tests):
        test_name = 'test_%s' % t[0]
        test = test_generator(t[1], t[2], t[3])
        setattr(TestPeriods, test_name, test)

    # unittest.main()
    suite = unittest.TestLoader().loadTestsFromTestCase(TestPeriods)
    unittest.TextTestRunner(verbosity=2).run(suite)

- Rabarberski

2个回答

3

你可以将跨越年底的时间段分为两个部分，然后进行比较。这将得到一个相当简单的递归函数，不需要任何特定于Python的功能：

def overlap(start_a, stop_a, start_b, stop_b):
    if start_a > stop_a:
        return overlap(start_a, 365, start_b, stop_b) or overlap(0, stop_a, start_b, stop_b)
    elif start_b > stop_b:
        return overlap(start_a, stop_a, start_b, 365) or overlap(start_a, stop_a, 0, stop_b)
    else:
        return start_a <= stop_b and start_b <= stop_a

def doesOverlap(A, B):
    return overlap(A.start, A.stop, B.start, B.stop)

- niemmi

不错的解决方案，特别是使用递归。 - Rabarberski

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- 6502 · Accepted Answer

def overlap(a0, a1, b0, b1):
    # First we "lift" the intervals from the yearly "circle"
    # to the time "line" by adjusting the ending date if
    # ends up before starting date...
    if a1 < a0: a1 += 365
    if b1 < b0: b1 += 365

    # There is an intersection either if the two intervals intersect ...
    if a1 > b0 and a0 < b1: return True

    # ... or if they do after moving A forward or backward one year
    if a1+365 > b0 and a0+365 < b1: return True
    if a1-365 > b0 and a0-365 < b1: return True

    # otherwise there's no intersection
    return False