c++ - 整数对列表中的最大数量

Question

我有一个整数对列表，试图找到重叠对的最大数量。

例如，(1,4)、(2,5)、(3,6) 返回 3；另一个例子 (1,4) (2,8) (5,6) return 2;

我正在考虑用第一个整数(较小的第一个)和打破平局(较大的第二个)对对进行排序，我将最宽的对放在开头。然后从第一对开始找到与其余部分的重叠，每次都更新重叠直到找到最大计数。然后继续第二对……然后找到最大计数。 O(N^2)

我不确定这是否有效。

这里有什么想法或更好的算法吗？

Answer 1

这将取第二个元素的最大值并返回给定最大第二个元素的第一个元素。如果您想要不同的东西，请更新您的问题以澄清:

#include <algorithm>
#include <iostream>
#include <vector>
#include <utility>

bool choose_second(const std::pair<int, int> &lhs,
                   const std::pair<int, int> &rhs) {
    return lhs.second < rhs.second ;
}

int main(int argc, char *argv[]) {
    std::vector<std::pair<int,int> > v1 = {
        std::make_pair(1, 4),
        std::make_pair(2, 5),
        std::make_pair(3, 6)
    };

    std::vector<std::pair<int,int> > v2 = {
        std::make_pair(1, 4),
        std::make_pair(2, 8),
        std::make_pair(5, 6)
    };

    auto max1 = std::max_element(v1.begin(), v1.end(), choose_second);
    auto max2 = std::max_element(v2.begin(), v2.end(), choose_second);

    std::cout << max1->first
              << std::endl
              << max2->first
              << std::endl;
}