In this HackerEarth Noor and his pond problem solution Noor is going fish farming. There are N types of fish. Each type of fish has size(S) and eating factor(E). A fish with eating factor of E, will eat all the fish of size .

Help Noor to select a set of fish such that the size of the set is maximized as well as they do not eat each other.


HackerEarth Noor and his pond problem solution


HackerEarth Noor and his pond problem solution.

#include <bits/stdc++.h>
using namespace std;

string toZero(int n)
{
string ret;
for(int i = 0; i < 2;i ++) ret.push_back(n%10 + '0'), n/=10;
reverse(ret.begin(), ret.end());
return ret;
}

int main()
{
int t;
cin >>t;
assert(t >= 1 && t <= 3);
while(t--){
int n;
cin >> n;
assert(n >= 1 && n <= 100000);

vector< pair<int,int> > vec;
for(int i = 0; i < n; i ++ ){
int s,e;
cin >> s >> e;
assert(s >= 1 && s <= 1000000000);
assert(e >= 1 && e <= 1000000000);
assert(s > e);
vec.push_back( make_pair(e,1));
vec.push_back( make_pair(s,-1));
}
sort(vec.begin(), vec.end());
int ans = 0, cum = 0;
for(int i = 0; i < vec.size(); i ++){
cum += vec[i].second;
ans = max(ans , cum);
}
cout << ans << endl;
}
}

//}