split-stay

Split Stay — Two-Listing Date Coverage

一亩三分地

Given a set of Airbnb listings, each with a list of available days, and a requested date range, return every pair of two distinct listings whose combined availability covers the range with no overlap (the first listing covers a contiguous prefix, the second covers the remainder).

Example

A - [1,2,3,6,7,10,11]
B - [3,4,5,6,8,9,10,13]
C - [7,8,9,10,11]
range = [3, 11]
expected = [(B, C)]   # B covers 3-6, C covers 7-11

暴力解法 brute force

直接解法：遍历每一对组合，然后判断是否可以覆盖[start, end]区间，判断方法也比较简单，A先和B先各试一次就行

时间复杂度 $N^2 \times M$

bitmask

用bitmask表示每个民宿的覆盖时间，然后同样遍历组合，用位操作帮助加速判断

有一个技巧是统计每一个民宿prefix和suffix的连续长度，这样两个民宿的prefix+suffix（或相反）相加和end-start+1比较即可

prefix length

1. 根据bitmask获取~missing，注意这里判断下如果missing为0，说明是全部覆盖的
2. 对missing找到最低位的1，说明更低的部分是连续的0，也就是民宿连续覆盖的天数
3. 最低位的1 bit位置-1即可

获取最低位的1方法如下，这里有个基础知识，-x=~x+1，即对x取反然后+1，所以两个相与，得到就是最低位的1

x & -x

suffix length

1. 获取missing，同样进行判0
2. 获取最高位的1，说明更高位都是连续0
3. length - pos即可

最高位的1 Python用 bit_length()即可

def find_split_stays(
    availability: Mapping[str, List[int]],
    start_day: int,
    end_day: int
) -> List[Tuple[str, ...]]:
    # convert day to bitmask
    prefix = {}
    suffix = {}
    length = end_day - start_day + 1
    days_mask = (1 << length) - 1
    for key, days in availability.items():
        bitmask = 0
        for day in days:
            if day >= start_day and day <= end_day:
                delta = day - start_day
                bitmask |= (1 << delta)
        """
        prefix_len continuous 1 bit from low position
        1. missing = mask ^ all days
        2. find missing lowest 1 pos
        3. pos - 1
        """
        missing = days_mask ^ bitmask
        if missing == 0:
            prefix_len = length
        else:
            lowest_bit = missing & -missing
            prefix_len = lowest_bit.bit_length() - 1

        """
        suffix_len continuosu 1 bits from high position
        1. get missing
        2. get missing highest 1 bit pos
        3. length - pos
        """
        if missing == 0:
            suffix_len = length
        else:
            suffix_len = length - missing.bit_length()

        prefix[key] = prefix_len
        suffix[key] = suffix_len
        # print(start_day, end_day, key, days, prefix_len, suffix_len)

    # traverse and check each pair
    result = []
    length = end_day - start_day + 1
    for house, pre in prefix.items():
        if pre == length:
            result.append(tuple([house]))
    for a, b in combinations(availability.keys(), 2):
        if prefix[a] == length:
            continue
        if prefix[b] == length:
            continue
        # check overlap
        valid = False
        if prefix[a] > 0 and suffix[b] > 0 and prefix[a] + suffix[b] >= length:
            valid = True
        if suffix[a] > 0 and prefix[b] > 0 and suffix[a] + prefix[b] >= length:
            valid = True
        if valid:
            result.append(tuple([a, b]))
    return result