lsquang
BAN USERx, y: interval.
x is not intersected with y:
x.second (end) <= y.first (start)
or x.first >= y.second.
the idea is so simple.
so an interval x. find the number of interval y where y.second <= x.first or y.first >= x.second.
y.second <= x.first : O(logN) if we have a vector of sorted start
y.first >= x.second: O(logN) if we have a vector of sorted end.
int maxint1(const std::vector< std::pair<int, int> > &its) //N^2
{
std::vector<int> starts;
std::vector<int> ends;
for (int i = 0; i != (int) its.size(); ++i) starts.push_back(its[i].first);
for (int i = 0; i != (int) its.size(); ++i) ends.push_back(its[i].second);
std::sort(starts.begin(), starts.end());
std::sort(ends.begin(), ends.end());
int maxnc = 0;
int maxid = 0;
for (int i = 0; i != (int) its.size(); ++i)
{
int nleft = std::lower_bound(ends.begin(), ends.end(), its[i].first) - ends.begin();
int nright = std::upper_bound(starts.begin(), starts.end(), its[i].second) - starts.begin();
// std::cout << nleft << " " << nright << " " << (int) its.size() - nright << "\n";
int nc1 = its.size() - nleft - (its.size() - nright);
int nc = 0;
for (int j = 0; j != (int) its.size(); ++j)
if (match(its[i], its[j])) nc ++;
if (nc > maxnc) { maxnc = nc; maxid = i;}
if (nc != nc1) {
std::cout << "error " << nc << " " << nc1 << "\n";
}
}
std::cout << maxnc << " " << maxid << "\n";
return maxnc;
}
Your solution is correct with tiny correction.
" Everything on the upper left of the middle 1 : not exactly." not exactly.
O(N,N) = 3* O(N/2,N/2);
O(N^2) = 3 *O(N/4) + 1;
O(2logN/log(4/3)) --> O(logN).
- lsquang July 26, 2016