段的起点和终点以 vector 的起点和终点给出。点列表以 vector 点给出。任务是找到包含每个点的线段数。
在我的解决方案中,起点,终点和点的每个元素分别被赋予了标签l,p和r,并存储在 vector 对中。然后,对 vector 首先按第一个元素排序,然后按第二个元素排序。最后,我遍历对 vector ,如果是起点,则增加变量的覆盖率;如果是终点,则减少变量的覆盖率;然后将其赋值给答案。
该算法似乎是正确的,但时间复杂度为O(nlog(n)),但超过了时间限制。代码的哪一部分慢?
代码:

vector<int> fast_count_segments(vector<int>& starts, vector<int>& ends, vector<int>& points) {
    vector<int> cnt(points.size());
    const int left_label = 1, point_label = 2, right_label = 3;
    std::map<int, std::set<int>> orig_point_map;
    vector<pair<int,int>> pairs(2*starts.size()+points.size());
    int k = 0;
    for (auto& i : starts)
    {
        pairs[k++] = std::make_pair(i, left_label);
    }
    for (auto& i : ends)
    {
        pairs[k++] = std::make_pair(i, right_label);
    }
    for (auto i = 0;i < points.size();i++)
    {
        int point = points[i];
        pairs[k++] = std::make_pair(point, point_label);
        orig_point_map[point].emplace(i);
    }

    std::sort(pairs.begin(), pairs.end());
    int coverage = 0;
    for (auto& x : pairs) {
        if (x.second == 1) {
            coverage++;
        }
        else if (x.second == 3) {
            coverage--;
        }
        else {
            std::set<int> indices = orig_point_map[x.first];
            for(auto i : indices) {
                cnt[i] = coverage;
            }
        }
    }
    return cnt;
}

最佳答案

尽管复杂度很高,但是您会创建很多副本,而这些副本可以避免。
您可以使用修改后的版本:

std::vector<int> fast_count_segments(std::vector<int> starts,
                                     std::vector<int> ends,
                                     const std::vector<int>& points) {
    std::vector<int> cnt(points.size());
    std::vector<std::pair<int, int>> pairs(points.size());

    for (auto i = 0u; i != points.size(); ++i) {
        pairs[i] = std::make_pair(points[i], i);
    }
    std::sort(starts.begin(), starts.end());
    std::sort(ends.begin(), ends.end());
    std::sort(pairs.begin(), pairs.end());
    int coverage = 0;
    auto it_start = starts.begin();
    auto it_end = ends.begin();
    for (auto& x : pairs) {

        while (it_start != starts.end() && *it_start <= x.first) {
            ++it_start;
            ++coverage;
        }
        while (it_end != ends.end() && *it_end < x.first) {
            ++it_end;
            --coverage;
        }
        cnt[x.second] = coverage;
    }
    return cnt;
}

10-06 05:08
查看更多