整數對列表中的最大數

Question

我有一個整數對列表，試圖找到重疊對的最大數目。例如，（1,4），（2,5），（3,6）返回3;例如，（1,4），（5），（6）返回3。 另一個例子（1,4）（2,8）（5,6）返回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; 
}