c++ - 计算 map 内的重叠时间 C++

Question

我有一个 key = startTime 和 value = endTime 的 map ，如下所示:

map<uint32_t,uint32_t>time_map;

(uint32_t 是 unsigned __int32，但这与这里无关)。

我想计算这些值中有多少个重叠值(代表连接的开始时间和结束时间，因此实际上有多少个重叠连接)。

哪种计算方法最快？ std::map 中是否有任何函数/方法可以解决此类问题？

---

编辑:就原始问题不清楚而言，其想法是计算任何给定时间点的最大重叠连接数。这意味着，考虑到这些时间:

start 100 - end 1000 / start 120 - end 200 / start 250 - end 400 / start 600 - end 800

答案是 2(1 与 2、1 与 3、1 与 4，但其他都不相互)

Answer 1

我会首先使用一种简单的方法，使用边 table ；它将接近扫线算法。

想法:

• 按顺序迭代连接(此处按开始时间排序)
• 保留一组当前涉及的连接

诀窍是有效地跟踪连接，尤其是何时删除它们；优先级队列对此非常有用。

一些帮助:

struct Connection {
    uint32_t start;
    uint32_t end;
}; // struct Connection

// WATCH OUT:
// std::priority_queue only let you access the MAXIMUM element, so the predicate
// is the OPPOSITE of what we usually write...
struct OrderByEnd {
    bool operator()(Connection const& left, Connection const& right) const {
        if (left.end > right.end) { return true; }
        if (left.end < right.end) { return false; }
        return left.start > right.start;
    }
}; // struct OrderByEnd

using CurrentlyOverlappingType = std::priority_queue<Connection, std::deque<Connection>, OrderByEnd>;

然后，我们扫荡:

size_t countMaxNumberOfOverlaps(std::map<uint32_t, uint32_t> const& connections) {
    if (connections.empty()) { return 0; }

    size_t max = 0;
    CurrentlyOverlappingType currentlyOverlapping;

    for (auto const& con: connections) {
        // Purge no longer overlapping connections
        while (not currentlyOverlapping.empty() and currentlyOverlapping.top().end < con.first) {
            currentlyOverlapping.pop();
        }

        // Debug:
        if (not currentlyOverlapping.empty()) {
            std::cout << "[" << con.first << ", " << con.second <<
                "] is overlapping with: " << currentlyOverlapping.size() << " connections\n";
        }

        // The current connection is necessarily overlapping with itself
        currentlyOverlapping.push(Connection{con.first, con.second});

        max = std::max(max, currentlyOverlapping.size());
    }

    return max;
} // countMaxNumberOfOverlaps

和it works as expected :

[120, 200] is overlapping with: 1 connections
[250, 400] is overlapping with: 1 connections
[600, 800] is overlapping with: 1 connections
Max number of overlaps: 2

复杂性更难以理解。您必须扫描整组连接，但每一步的工作量与当前重叠连接的数量成正比......

• 最坏情况复杂度:O(N * log(N)) 我想说(因为插入优先级队列是对数的)
• 平均情况复杂度:O(N * log(O))，其中 O 是重叠连接的数量

注:在算法分析中，我认为purge部分的复杂度是摊余常数；我们知道项目将被清除，因此我们可以在插入成本中考虑它们的清除。插入 N 个项目，将清除 N 个项目。作为清除过程的一部分执行的比较次数(我认为)也是摊销常数(所有项目的总数上限为 2N)，尽管它是直觉而不是计算。因此，清除的成本与将项目插入优先级队列的成本相形见绌，每个项目为 log(O)。