CODEWITHSUNDEEP
c++
Minfeng James Wang
Minfeng James Wang

Reputation: 15

Max number in a list of integer pairs

I have a list of pair integers , trying to find the max number of the overlapped pairs.

for example, (1,4), (2,5), (3,6) return 3; another example (1,4) (2,8) (5,6) return 2;

I am thinking sort the pairs with the first integer (smaller first) and breaking tie (the bigger second) which I put the most wide open pairs at the beginning. And then starting with the 1st pair find the overlap with the rest, every time renew the overlap till find max count. Then proceed with the second pair...... Then find the max count. O(N^2)

I am not sure if this is working.

Any ideas or better algorithm here?

Upvotes: 0

Views: 1063

Answers (1)

b4hand
b4hand

Reputation: 9770

This will take the maximum of the second element and return the first element given that maximal second element. If you want something different, please update your question to clarify:

#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;
}

Upvotes: 1

Related Questions