给定一个数查找所在区间或者查找所有重叠区间的算法总结

区间操作相关的算法

1.前言

在个人项目的研究中遇到一个和区间操作相关的场景，涉及到给定一个数，查找对应的区间和查找所有重叠的区间。现对这个问题的算法做个总结。

例1.给定若干个区间：

[1,3],[5,10],[21,26]

然后给定若干个数:0,1,2,3,8,26,29，查找这些数对应的区间，找不到就返回空。预期结果是

null
[1,3]
[1,3]
[1,3]
[5,10]
[21,26]
null

例2.给定若干个区间：

[1,3],[2,6],[10,29],[10,14],[22,78],[100,133]

找出以上区间中所有重叠的区间，找不到返回空。预期结果是

[1,3],[2,6]
[10,29],[10,14]
[10,29],[22,78]

2.算法

2.1.查找区间算法

可以借用二分查找的思想，首先可以在插入区间的时候按顺序插入。借用例1的数据，默认以区间左端点数值从小到大的顺序将区间插入，得到

a = [1,3,5,10,21,26]

对于新的序列有这么两个特点：

1. 偶数位是原区间的左端点，奇数位是原区间的右端点。
2. 序列的长度为偶数。

2.1.2.流程图

所以结合二分查找与序列的特点，就能在O(n) = log(n)的时间复杂度下找到对应区间。

2.1.3.代码实现

$注：使用c++20$

auto find_segment(_Ty number)->std::optional<const IntervalNode<_Ty>>
{
    int l = 0;
    int h = m_segments.size() - 1;

    while (l <= h)
    {
        int m = (l + h) / 2;

        if (m & 1)
        {
            if (number >= m_segments[m - 1] && number <= m_segments[m])
            {
                return IntervalNode<_Ty>
                {
                    .left = m_segments[m - 1],
                    .right = m_segments[m]
                };
            }

            if (number < m_segments[m - 1]) h = m - 1;
            else if (number > m_segments[m]) l = m + 1;
        }
        else
        {
            if (number >= m_segments[m] && number <= m_segments[m + 1])
            {
                return IntervalNode<_Ty>
                {
                    .left = m_segments[m],
                    .right = m_segments[m + 1]
                };
            }

            if (number < m_segments[m]) h = m - 1;
            else if (number > m_segments[m + 1]) l = m + 1;
        }
    }

    return std::nullopt;
}

2.2.查找所有重叠区间的算法

借用前言中提到的例2中的数据，默认以区间左端点和右端点数值从小到大的顺序将区间插入，得到

a = [1,3,2,6,10,14,10,29,22,78,100,133]

对于新的序列有这么两个特点：

1. 偶数位是原区间的左端点，奇数位是原区间的右端点。
2. 序列的长度为偶数。

2.2.1.算法流程图

2.2.2.代码实现

$注：使用c++20$

auto find_all_overlaps()->std::vector<std::tuple<const IntervalNode<_Ty>, const IntervalNode<_Ty>>>
{
    std::vector<std::tuple<const IntervalNode<_Ty>, const IntervalNode<_Ty>>> findOverlaps;

    for (int i = 0; i < m_segments.size() / 2 - 1; i++)
    {
        for (int j = i + 1; j < m_segments.size() / 2; j++)
        {
            if (m_segments[2 * i] <= m_segments[2 * j] && m_segments[2 * i + 1] >= m_segments[2 * j])
            {
                std::tuple<const IntervalNode<_Ty>, const IntervalNode<_Ty>> overlaps
                {
                    IntervalNode<_Ty>
                    {
                        .left = m_segments[2 * i],
                        .right = m_segments[2 * i + 1]
                    },
                    IntervalNode<_Ty>
                    {
                        .left = m_segments[2 * j],
                        .right = m_segments[2 * j + 1]
                    },
                };

                findOverlaps.push_back(overlaps);
            }
        }
    }

    return findOverlaps;
}

3.测试

class CCIntervalTester
{
public:
    auto TestFindSegment()->void
    {
        Algorithm::CCInterval<int> interval;

        interval.add_segment(1, 3);
        interval.add_segment(5,10);
        interval.add_segment(21,26);

        srand(time(NULL));

        for (int i = 0; i < 20; i++)
        {
            auto r = rand() % 30;
            const auto& f = interval.find_segment(r);
            if (f != std::nullopt)printf("%d in [%d,%d]\n", r, f.value().left, f.value().right);
            else printf("%d not found.\n",r);
        }
    }

    auto TestFindAllOverlaps()->void
    {
        Algorithm::CCInterval<int> interval;
        interval.add_segment(1, 3);
        interval.add_segment(2, 6);
        interval.add_segment(10, 29);
        interval.add_segment(10, 14);
        interval.add_segment(22, 78);
        interval.add_segment(100, 133);

        const auto& o = interval.find_all_overlaps();

        for (const auto& i : o)
        {
            printf(
                "[%d,%d] and [%d,%d]\n",
                std::get<0>(i).left, std::get<0>(i).right,
                std::get<1>(i).left, std::get<1>(i).right);
        }
    }
};

完整代码请移步至我的github：https://github.com/singlefreshBird/Algorithm