chuckNorris
BAN USERi test my code in production
can be done using union-find data structure with one pass on the matrix.
time: O(log*(NxN))
a single node could be considered as a sub-tree(connected and non-cyclic graph)
O(n) one traverse, use a hash table to insert the nodes to, and check if the current node was previously added, if so then return true. after the traverse finish, means there's no duplicates
Here's a working C++ solution
#include <algorithm>
#include <map>
#include <iostream>
using namespace std;
/************************************************************/
typedef pair<int, int> Range;
//auxilary function.
//return true if r2 is contained in r1
bool isContained(Range r1, Range r2) {
return (r1.first <= r2.first) && (r1.second >= r2.second);
}
//------------------------------------------
void getMaxRange(Range& max, const vector<Range> ranges) {
max = ranges[0];
for(size_t i = 0; i < ranges.size(); ++i) {
max = (isContained(ranges[i] ,max)) ? ranges[i] : max;
}
}
//------------------------------------------
void printOptimalRanges(vector<Range>& ranges) {
if(ranges.empty()) {
return;
}
sort(ranges.begin(), ranges.end());
Range current, previous, max;
getMaxRange(max, ranges);
for(size_t i = 1; i < ranges.size(); ++i) {
current = ranges[i];
previous = ranges[i-1];
if(isContained(max, current) && isContained(max, previous)) {
continue;
} else if(!isContained(previous, current)) {
cout << current.first << " " << current.second << endl;
}
}
cout << max.first << " " << max.second << endl;
}
/************************************************************/
int main() {
//int arr[] = {0,1,2,3,4,5,6};
//printAllPairsSumToN(arr,7, 6);
vector<Range> ranges;
Range r = make_pair(2,6);
ranges.push_back(r);
r = make_pair(1,21);
ranges.push_back(r);
r = make_pair(3,5);
ranges.push_back(r);
r = make_pair(20,21);
ranges.push_back(r);
r = make_pair(1,40);
ranges.push_back(r);
printOptimalRanges(ranges);
return 0;
}
you must find the max range which most of the ranges are contained in it.
- chuckNorris November 19, 2015
- chuckNorris January 16, 2017