Максимальное число в списке целых пар

Question

У меня есть список целых чисел, пытаясь найти максимальное количество перекрывающихся пар.

например, (1,4), (2,5), (3,6) return 3; другой пример (1,4) (2,8) (5,6) return 2;

Я думаю, что сортировать пары с первым целым числом (меньше первого) и разрывать галстук (большую секунду), которую я ставил в начале самые широкие открытые пары. И затем, начиная с 1-й пары, найдите перекрытие с остальным, каждый раз обновляя перекрытие, пока не найдете максимальное количество. Затем переходите к второй паре ...... Затем найдите максимальное количество. 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; 
}