计算与给定会议时间相交的区间数

背景介绍

在日常生活中，我们常常需要处理时间问题，例如判断某两个时间段是否有重叠部分。在会议安排中也有类似的问题，需要计算与给定会议时间相交的区间数。这个问题可以用算法来解决。

问题分析

给定若干时间段，求与给定时间段相交的区间数。为了方便，我们将时间段按照开始时间从小到大排序。

暴力算法

暴力算法的思路是，对于每个时间段，枚举其与其他时间段是否有交集。若有，计数器加1。

int countIntersect(vector<pair<int, int>> intervals, pair<int, int> meeting) {
    int count = 0;
    for (int i = 0; i < intervals.size(); i++) {
        if (intervals[i].second < meeting.first) {
            continue;
        }
        if (intervals[i].first > meeting.second) {
            break;
        }
        count++;
    }
    return count;
}

上述算法的时间复杂度为O(n^2)，当时间段较多时效率较低。在实际应用中，可以使用更高效的算法来解决此问题。

二分查找算法

如果对时间段按开始时间从小到大排序，那么可以使用二分查找算法来加速计算与给定时间段相交的区间数。

对于一个时间段，我们可以在排序后的时间段序列中二分查找，找到所有结束时间小于其开始时间的时间段，以及所有开始时间大于其结束时间的时间段，这些时间段与给定时间段不重叠，可以跳过。

剩下的时间段必然与给定时间段有交集，可以直接计数。

int countIntersect(vector<pair<int, int>> intervals, pair<int, int> meeting) {
    int count = 0;
    int l = 0, r = intervals.size() - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (intervals[mid].second < meeting.first) {
            l = mid + 1;
        } else if (intervals[mid].first > meeting.second) {
            r = mid - 1;
        } else {
            count++;
            int cur = mid - 1;
            while (cur >= 0 && intervals[cur].second >= intervals[mid].first) {
                count++;
                cur--;
            }
            cur = mid + 1;
            while (cur < intervals.size() && intervals[cur].first <= intervals[mid].second) {
                count++;
                cur++;
            }
            break;
        }
    }
    return count;
}

二分查找算法的时间复杂度为O(nlogn)，更适合处理大量时间段的情况。

总结

给定若干时间段，求与给定时间段相交的区间数这个问题可以用暴力算法或二分查找算法来解决。暴力算法的时间复杂度为O(n^2)，在处理大量时间段时效率较低。二分查找算法的时间复杂度为O(nlogn)，更适合处理大量时间段的情况。