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