Google Interview Question
Software Engineer InternsCountry: United States
You can avoid removing from optList by changing your sort: if o.a==this.a then take the longer range first. This way it can't happen that the coming range contains previous one.
Do the ranges strictly include each other or they might overlap only partially, like in this example:
[[2:6], [3:8], [5:20]]?
If they were "overlapping only partially", we had nothing to do, because the task asks to remove subarrays. So it's both.
What do you mean nothing to do?
in the example we could have minimized it to [[2:20]] because it contains all ranges from original input.
So is the input "[[2:6], [3:8], [5:20]]" valid for this question? Is the task asks to only remove ranges that are completely included in other ranges or to minimize number of ranges so that all numbers from original input are still covered (by smaller number of ranges)?
This is incorrect solution. For example: [2, 30] [3, 21] [4,26]
In above solution, [4,26] should be absorbed by [2, 30] but the sorted sequence will never compare [4, 26] to [2, 30]
No, [4,26] will not be compared to [2,30], but it will be compared to [3,41] and will be ignored, because it's subarray.
The solution is correct.
I think the solution has a problem:
Consider the case [2, 4] [3, 6] [5, 8]
The ideal solution should be [2, 4] [5, 8]
But using the above, it will produce [2,4] [3,6] [5, 8]
If you need to preserve the subarray then you cannot sort to begin with ! Then it completely invalidates the above solution as it will change the order of entries !
@Anon, what do you mean by "ideal solution"? [2,4] [3,6] [5, 8] is correct solution, no range is contained in another range, so no range is removed.
@ashish.kaila, have you heard of Arrays.copyOf?
@damluar: I think the question requires some clarification from the post.
If the solution involves just checking the previous and next subarray, then the above solution is fine.
But, my guess is that they would want an optimal solution. For example, [2,4] [3,6] [5, 8], we would want [2,4][5,8] since it covers the entire range from 2-8.
We don't want to include [3,6] even though it is not included in the prev/next range since it would make no difference to the range [2-8]. This would involve dynamic programming.
What about [1,2][3,4],[1,5]?
expect output is [1,5]
but the program above will produce [1,2][1,5] I think.
> What about [1,2][3,4],[1,5]?
> expect output is [1,5]
> but the program above will produce [1,2][1,5] I think.
After the sorting step, the array will become [1,2][1,5][3,4]. Therefore, the final output will be [1,5].
function getArrayRange(first, last){
var arrRange =[];
for(var i=first; i<=last; i++){
arrRange.push(i);
}
return arrRange
}
//console.log(getArrayRange(7,21))
function removeSubArr(arr){
var obj = {};
var fullArr = [];
for (var i=0; i<arr.length; i++){
for(var j=0; j<arr[i].length; j++){
fullArr.push(getArrayRange(arr[i][0], arr[i][1]));
obj[arr[i]] = getArrayRange(arr[i][0], arr[i][1]);
}
}
for(var prop in obj){
if(obj.hasOwnProperty(prop)){
for(var i =0; i< fullArr.length; i++){
if(subArrCheck(obj[prop], fullArr[i]) == true){
fullArr.splice(i,1);
}
}
}
}
return fullArr;
}
function subArrCheck(arr, subarr) {
var i, found, j;
for (i = 0; i < 1 + (arr.length - subarr.length); ++i) {
found = true;
for (j = 0; j < subarr.length; ++j) {
if (arr[i + j] !== subarr[j]) {
found = false;
break;
}
}
if (found) return true;
}
return false;
};
console.log(removeSubArr([[2, 6],[3, 5],[7, 21],[20, 21]]));
How about a merge sort? O(n*log(n)) time, O(n) memory (n-ah, not in this python pseudocode)
The idea is the following - in both subarrays ranges are sorted by their left bound, shortest first. If one range contains another, just skip it. However, if we have two arrays
(a1, ...) (a2, ....), ...
(b1, ...) (b2, ...), ...
There are 3 cases
1) a1 < b1, then we are sure that (a1, ...) is not a subarray of any of (b1, ...), (b2, ...), etc. Also (b1, ...) is not a subarray of (a1, ...), so neither (b2, ...), (b3, ...) are, since they are already known to be not a subarray of (b1, ...) - emit (a1, ...)
2) a1 = b1, - basically can't happen, since then (a1, ...) would be sub-range of (b1, ...) or vice-versa
3) a1 > b1, then we are sure that (b1, ...) is not a subarray of any (a1, ...), (a2, ...), etc - emit (b1, ...)
def dumb_algo(ranges):
"""Dumb algorithm for checking correctness of merge sort approach"""
result = []
removed = set()
for i, candidate in enumerate(ranges):
for j, other in enumerate(ranges):
if j in removed:
continue
if i != j and contains(other, candidate):
removed.add(i)
break
else:
result.append(candidate)
return result
def contains(who, whom):
return who[0] <= whom[0] <= whom[1] <= who[1]
def merge_sort(ranges):
if len(ranges) <= 1:
return ranges
mid = len(ranges) / 2
left = merge_sort(ranges[:mid])
right = merge_sort(ranges[mid:])
result = []
i = j = 0
while i < len(left) and j < len(right):
l = left[i]
r = right[j]
if contains(l, r):
j += 1
elif contains(r, l):
i += 1
else:
if l < r:
result.append(l)
i += 1
else:
result.append(r)
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
import random
for i in xrange(500):
ranges = []
for j in xrange(200):
left = random.randrange(100)
right = random.randrange(left, 101)
ranges.append((left, right))
assert sorted(merge_sort(ranges)) == sorted(dumb_algo(ranges))
Complexity: O(n log n) in time => due to the initial sort
If the input was already sorted the complexity would be O(n).
public static class Interval {
public Interval(int s, int e) {
this.start = s;
this.end = e;
}
public int start;
public int end;
}
public static List<Interval> clean(List<Interval> ranges) {
Collections.sort(ranges, new Comparator<Interval>() {
@Override
public int compare(Interval int1, Interval int2) {
return int1.start - int2.start;
}
});
List<Interval> output = new ArrayList<>();
int start = ranges.get(0).start;
int end = ranges.get(0).end;
for (int i = 1; i < ranges.size(); i++) {
if (ranges.get(i).start <= end) {
if (ranges.get(i).end > end)
end = ranges.get(i).end;
} else {
Interval interval = new Interval(start, end);
output.add(interval);
start = ranges.get(i).start;
end = ranges.get(i).end;
}
}
Interval interval = new Interval(start, end);
output.add(interval);
return output;
}
I don't think so, since this is not a reduction problem, otherwise the example OUTPUT would've been [(2,21)]
Sort the pairs, and then check each element if its within the range of the previous one. Replace it accordingly.
public class ArrayRangeSubset {
public static class Pair implements Comparable<Pair>{
Integer a;
Integer b;
public Pair(int a, int b)
{
this.a = a;
this.b = b;
}
public boolean isInside(Pair other)
{
return (other!=null &&
other.a <= other.b &&
other.a <= this.a &&
other.b >= this.b);
}
@Override
public int compareTo(Pair o) {
return o.a==this.a?b.compareTo(o.b):
a.compareTo(o.a);
}
@Override
public String toString() {
return "("+a+", "+b+")";
}
}
public static ArrayList<Pair> smallerSubArray(Pair[] data)
{
Arrays.sort(data);
ArrayList<Pair> optList = new ArrayList<Pair>();
optList.add(data[0]);
for (int i=1;i<data.length;i++)
{
if (!data[i].isInside(optList.get(optList.size()-1)))
{
if (optList.get(optList.size()-1).isInside(data[i])) {
optList.remove(optList.size()-1);
}
optList.add(data[i]);
}
}
return optList;
}
public static void main(String[] args) {
Pair[] data={ new Pair(3,5), new Pair(2,6), new Pair(2,8), new Pair(20,21), new Pair(8,20) } ;
ArrayList<Pair> sm = smallerSubArray(data);
System.out.println(sm);
}
}
public class ArrayRangeSubset {
public static class Pair implements Comparable<Pair>{
Integer a;
Integer b;
public Pair(int a, int b)
{
this.a = a;
this.b = b;
}
public boolean isInside(Pair other)
{
return (other!=null &&
other.a <= other.b &&
other.a <= this.a &&
other.b >= this.b);
}
@Override
public int compareTo(Pair o) {
return o.a==this.a?b.compareTo(o.b):
a.compareTo(o.a);
}
@Override
public String toString() {
return "("+a+", "+b+")";
}
}
public static ArrayList<Pair> smallerSubArray(Pair[] data)
{
Arrays.sort(data);
ArrayList<Pair> optList = new ArrayList<Pair>();
optList.add(data[0]);
for (int i=1;i<data.length;i++)
{
if (!data[i].isInside(optList.get(optList.size()-1)))
{
if (optList.get(optList.size()-1).isInside(data[i])) {
optList.remove(optList.size()-1);
}
optList.add(data[i]);
}
}
return optList;
}
public static void main(String[] args) {
Pair[] data={ new Pair(3,5), new Pair(2,6), new Pair(2,8), new Pair(20,21), new Pair(8,20) } ;
ArrayList<Pair> sm = smallerSubArray(data);
System.out.println(sm);
}
}
O(NLogN) solution, based on sorting by Start value and then using stack to handle overlaps
class Program
{
class range
{
public int start;
public int end;
public range( int _start, int _end )
{
this.start = _start;
this.end = _end;
}
}
static void Main( string[] args )
{
int n = int.Parse( Console.ReadLine() );
List<range> ranges = new List<range>();
for ( int i = 0; i < n; i++ )
{
int[] arr = Console.ReadLine().Split().Select( x => int.Parse( x ) ).ToArray<int>();
ranges.Add( new range( arr[0], arr[1] ) );
}
var r = ranges.OrderBy( x => x.start ).ToList();
Stack<range> s = new Stack<range>();
s.Push( r[0] );
for ( int i = 1; i < r.Count; i++ )
{
range curr = s.Pop();
if ( r[i].start >= curr.start && r[i].end <= curr.end )
{
s.Push( curr );
continue;
}
else
{
s.Push( curr );
s.Push( r[i] );
}
}
foreach ( var kv in s )
Console.WriteLine( "{0}-{1}", kv.start, kv.end );
}
}
}
Sorting is O(n log n). Finding maximum coverage with minimum items is O(n).
c++, implementation
struct sort_first_second {
bool operator()(const pair<int, int>& left, const pair<int, int>& right) {
if (left.first != right.first) return left.first < right.first;
return left.second < right.second;
}
};
void optimizeArray(vector<pair<int, int>>& arr) {
vector<pair<int, int>> result;
int i, limit, start, end, index;
if (arr.size() == 0) return;
sort(arr.begin(), arr.end(), sort_first_second());
limit = arr[arr.size() - 1].second;
start = arr[0].first;
end = start;
i = 0;
while (end < limit) {
index = -1;
while (i < arr.size()) {
if (arr[i].first <= start) {
if (arr[i].second > end) {
end = arr[i].second;
index = i;
}
} else {
if (index == -1) {
start = arr[i].first;
}
break;
}
i++;
}
if (index != -1) {
start = end;
result.push_back(arr[index]);
}
}
arr = result;
}
#include <vector>
#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;
vector<pair<int, int> > func(vector<pair<int, int> > list) {
vector<pair<int, int> > ans;
sort(list.begin(), list.end());
ans.push_back(list[0]);
for(int i=1; i<list.size(); i++) {
pair<int, int> tmp=*(ans.end()-1);
if(list[i].first>=tmp.first && list[i].second<=tmp.second) // this means that list[i] is completely within tmp
continue;
else if(tmp.first>=list[i].first && tmp.second<=list[i].second)
ans[ans.size()-1]=list[i];
else {
if(list[i].first<tmp.first && list[i].first<tmp.second) {
ans[ans.size()-1].first=list[i].first;
ans[ans.size()-1].second=tmp.second;
}
else
ans.push_back(list[i]);
}
}
return ans;
}
int main() {
vector<pair<int, int> > in, out;
in.resize(4);
in[0].first=2; in[0].second=6;
in[1].first=3; in[1].second=5;
in[2].first=7; in[2].second=21;
in[3].first=20; in[3].second=21;
out=func(in);
for(int i=0; i<out.size(); i++)
printf("%d %d\n", out[i].first, out[i].second);
return 0;
}
struct range {
int l, r;
}
struct range_comparator {
bool operator()(const ranges& l, const ranges& r) const {
return l.l < r.l || (l.l == r.l && l.r < r.r);
}
}
std::vector<range> merge_array_range(std::vector<range> ranges) {
std::sort(ranges.begin(), ranges.end(), range_comparator());
std::vector<range> res;
res.push_back(ranges.front());
for (int i = 1; ranges.length(); ++i) {
if (ranges[i].l <= res.back().l) {
if (res.back.r < ranges[i].r)
res.back.r = ranges[i].r;
} else {
res.push_back(ranges[i]);
}
}
return res;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct range {
range(int ll, int rr) : l(ll), r(rr) {}
int l, r;
};
struct range_comparator {
bool operator()(const range& l, const range& r) const {
return l.l < r.l || (l.l == r.l && l.r < r.r);
}
};
void print_ranges(vector<range>& ranges) {
for (vector<range>::iterator it = ranges.begin(); it != ranges.end(); ++it) {
cout << "(" << it->l << " " << it->r << ") ";
}
cout << endl;
}
vector<range> merge_array_range(vector<range>& ranges) {
sort(ranges.begin(), ranges.end(), range_comparator());
vector<range> res;
res.push_back(ranges.front());
for (int i = 1; i < ranges.size(); ++i) {
if (ranges[i].l <= res.back().r) {
if (res.back().r < ranges[i].r) {
res.back().r = ranges[i].r;
}
} else {
res.push_back(ranges[i]);
}
}
return res;
}
int main()
{
vector<range> ranges;
ranges.push_back(range(1, 5));
ranges.push_back(range(1, 3));
ranges.push_back(range(1, 7));
ranges.push_back(range(2, 3));
ranges.push_back(range(3, 5));
ranges.push_back(range(8, 9));
ranges.push_back(range(9, 17));
ranges.push_back(range(5, 6));
print_ranges(ranges);
vector<range> merged = merge_array_range(ranges);
print_ranges(merged);
return 0;
}
> (1 5) (1 3) (1 7) (2 3) (3 5) (8 9) (9 17) (5 6)
> (1 7) (8 17)
Sort the set by start, if start values are equivalent, sort in descending end order
Iterate over the sorted array and add to result array entries where the value of end exceeds the current max. Update max in this case.
Time Complexity: O(n log n) due to sorting
Sorting is not stable, and I was not sure if this was supposed to modify the original array or return a different array.
var Tuple = function(start, end) {
this.start = start;
this.end = end;
}
function removeRange(set) {
var endMax = 0;
var result = [];
if (set.length < 2) { return set; }
set.sort(function (a,b) {
if (a.start === b.start) {
return b.end - a.end;
} else {
return a.start - b.start;
}
});
endMax = set[0].end;
result.push(set[0]);
for (var i = 1; i < set.length; i++){
if (set[i].end > endMax) {
result.push(set[i]);
endMax = set[i].end;
}
}
return result;
}
// Execute
var set1 = [ new Tuple(2,6), new Tuple(3,5), new Tuple(7,21), new Tuple(20,21) ];
var set2 = [ new Tuple(1,5), new Tuple(1,3), new Tuple(1,7), new Tuple(2,3) ,
new Tuple(3,5), new Tuple(8,9), new Tuple(9,17), new Tuple(5,6)];
var set3 = [ new Tuple(1,10), new Tuple(3,3), new Tuple(4,7), new Tuple(10,30) ,
new Tuple(16,19), new Tuple(-1,9), new Tuple(9,31), new Tuple(9,29)];
console.log(removeRange(set1)); // Expected: [(2,6), (7,21)]
console.log(removeRange(set2)); // Expected: [(1,7), (8,9), (9,17)]
console.log(removeRange(set3)); // Expected: [(-1,9), (1,10), (9,31)]
This is the C++ solution.
Running time is O(n log n) due to the sorting.
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
struct range {
int start;
int end;
range(int s, int e): start(s), end(e) {}
};
bool compare(range* prev, range* after)
{
return prev->start <= after->start;
}
void merge_range (vector<range*>& input)
{
std::sort(input.begin(), input.end(), compare);
vector<range*>::iterator iter = input.begin();
range* cur = 0;
while (iter != input.end())
{
if (!cur)
{
cur = *iter;
iter++;
} else if (cur->end >= (*iter)->start)
{
cur->end = (cur->end > (*iter)->end)? cur->end : (*iter)->end;
iter = input.erase(iter);
} else {
cur = *iter;
iter++;
}
}
}
int main()
{
vector<range*> input;
input.push_back(new range(2,6));
input.push_back(new range(3,5));
input.push_back(new range(7,21));
input.push_back(new range(20,21));
merge_range(input);
for (int i= 0; i < input.size(); i++)
cout<<"( "<<input[i]->start<<", "<<input[i]->end<<" )"<<endl;
return 1;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector< pair<int,int> > vp;
int N, first, second;
cout<<"Array range length : ";
cin>>N;
cout<<"Input :"<<endl;
for(int i=0;i<N;i++){
cin>>first>>second;
vp.push_back(pair<int,int>(first,second));
}
//Skip if already sort
sort(vp.begin(), vp.end());
pair<int,int> temp = vp[0];
vector< pair<int,int> > ans;
ans.push_back(temp);
for(int i=1;i<vp.size();i++){
if(vp[i].first > temp.first && vp[i].second > temp.second){
ans.push_back(vp[i]);
temp = vp[i];
}
}
cout<<"[";
for(int i=0;i<ans.size();i++){
if(i!=0){
cout<<",";
}
cout<<"("<<ans[i].first<<","<<ans[i].second<<")";
}
cout<<"]"<<endl;
return 0;
}
void deletingSubarray(vector<vector<int>> & vecArray) {
set<int> badSet;
sort(vecArray.begin(), vecArray.end(), compare);
for(int i=0; i < vecArray.size(); ++i) {
if(badSet.find(i)== badSet.end()) {
for(int j=i+1; j< vecArray.size(); ++j) {
if(vecArray[j].front() == vecArray[i].front() || vecArray[j].back() <= vecArray[i].back()) {
badSet.insert(j);
}
}
}
}
for(int i=0; i< vecArray.size(); ++i) {
if(badSet.find(i)== badSet.end()) {
cout << "[" << vecArray[i].front() << ", " << vecArray[i].back() << "]" << endl;
}
}
}
void deletingSubarray(vector<vector<int>> & vecArray) {
set<int> badSet;
sort(vecArray.begin(), vecArray.end(), compare);
for(int i=0; i < vecArray.size(); ++i) {
if(badSet.find(i)== badSet.end()) {
for(int j=i+1; j< vecArray.size(); ++j) {
if(vecArray[j].front() == vecArray[i].front() || vecArray[j].back() <= vecArray[i].back()) {
badSet.insert(j);
}
}
}
}
for(int i=0; i< vecArray.size(); ++i) {
if(badSet.find(i)== badSet.end()) {
cout << "[" << vecArray[i].front() << ", " << vecArray[i].back() << "]" << endl;
}
}
}
void deletingSubarray(vector<vector<int>> & vecArray) {
set<int> badSet;
sort(vecArray.begin(), vecArray.end(), compare);
for(int i=0; i < vecArray.size(); ++i) {
if(badSet.find(i)== badSet.end()) {
for(int j=i+1; j< vecArray.size(); ++j) {
if(vecArray[j].front() == vecArray[i].front() || vecArray[j].back() <= vecArray[i].back()) {
badSet.insert(j);
}
}
}
}
for(int i=0; i< vecArray.size(); ++i) {
if(badSet.find(i)== badSet.end()) {
cout << "[" << vecArray[i].front() << ", " << vecArray[i].back() << "]" << endl;
}
}
}
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
bool compare(vector<int> vec1, vector<int> vec2) {
if(vec1.front()!= vec2.front())
return vec1.front() < vec2.front();
return vec1.end() > vec2.end();
}
void deletingSubarray(vector<vector<int>> & vecArray) {
set<int> badSet;
sort(vecArray.begin(), vecArray.end(), compare);
for(int i=0; i < vecArray.size(); ++i) {
if(badSet.find(i)== badSet.end()) {
for(int j=i+1; j< vecArray.size(); ++j) {
if(vecArray[j].front() == vecArray[i].front() || vecArray[j].back() <= vecArray[i].back()) {
badSet.insert(j);
}
}
}
}
for(int i=0; i< vecArray.size(); ++i) {
if(badSet.find(i)== badSet.end()) {
cout << "[" << vecArray[i].front() << ", " << vecArray[i].back() << "]" << endl;
}
}
}
My C# Solution, I am asuming the ranges in a sort order, if that is not the case the ranges must be sorted first:
Array.Sort(ranges, IComparer<int>);
The IComparer interface must be implemented comparing the first element of the range.
public int[][] CombineRanges(int[][] ranges)
{
int length = ranges.GetLength(0);
if (length <= 1)
return ranges;
List<int[]> result = new List<int[]>();
int[] p = ranges[0];
for (int i = 1; i < length; i++)
{
int[] current = ranges[i];
Debug.Assert(current.Length == 2);
if (current[0] <= p[1])
{
int[] np = new int[2];
np[0] = p[0];
np[1] = Math.Max(p[1], current[1]);
p = np;
}
else
{
result.Add(p);
p = current;
}
}
result.Add(p);
return result.ToArray();
}
def rmsubrange(rs):
"""Given an array of 'array ranges' (rs), return an optimized array by
deleting subarrays. Time complexity O(n*log(n)).
NOTE: Array range (2,6) represents (2,3,4,5,6)
>>> rmsubrange([(2, 6), (3, 5), (20, 21), (7, 21)])
[(2, 6), (7, 21)]
>>> rmsubrange([(10, 13), (1, 8), (2, 6), (15, 18), (12, 18)])
[(1, 8), (10, 13), (12, 18)]
"""
if not rs or len(rs) == 1:
return rs
rs.sort(key=lambda x: x[0])
rs_opt = []
for i in range(len(rs) - 1):
if rs[i]:
if not (rs[i][0] >= rs[i+1][0] and rs[i][1] <= rs[i+1][1]):
rs_opt.append(rs[i])
if rs[i+1][1] < rs[i][1]:
rs[i+1] = None
return rs_opt
if __name__ == '__main__':
import doctest
doctest.testmod()
Pretty sure I have a working solution (minus some sorry length input edge cases or whatever have you) You want to check for 2 things:
1) An interval is completely inside a previous interval
2) An interval is completely inside the merger of neighboring intervals. This only happens when the End of previous interval is equal or -1 of the Start of the Next interval.
def intervals(arr):
arr = sorted(arr, key = lambda x: (x[0],1/x[1]))
res = [arr[0]]
for i in range(1,len(arr)):
curr = arr[i]
# if previous interval 'completely covers' curr, skip
if curr[0] >= res[-1][0] and curr[1] <= res[-1][1]:
continue
else:
useCurr = True
for j in range(i+1,len(arr)):
# check if curr is 'covered' by it's neighbors. ie: [1,5][3,7][6,10].
# in this case we would not need [3,7]
if arr[j][0] == res[-1][1] or arr[j][0] == res[-1][1]+1:
if curr[1] <= arr[j][1]:
useCurr = False
else:
break
else:
break
if useCurr:
res.append(curr)
return(res)
test1 = [(2,6),(3,5),(7,21),(20,21)]
test2 = [(2,6),(3,9),(8,21),(20,21)]
print(intervals(test1)) -----OUTPUT----> [(2, 6), (7, 21)]
print(intervals(test2)) -----OUTPUT----> [(2,6),(3,9),(8,21),(20,21)]
In Java:
List<List<Integer>> rangeList = new ArrayList<>();
rangeList.add(Arrays.asList(7, 21));
rangeList.add(Arrays.asList(20, 21));
rangeList.add(Arrays.asList(2, 6));
rangeList.add(Arrays.asList(3, 5));
Set<List<Integer>> rangeForDeleteSet = new HashSet<>();
for (List<Integer> range : rangeList) {
int rangeStart = range.get(0);
int rangeEnd = range.get(1);
for (List<Integer> subRange : rangeList) {
if (range == subRange) {
continue;
}
int subRangeStart = subRange.get(0);
int subRangeEnd = subRange.get(1);
if (rangeStart <= subRangeStart && rangeEnd >= subRangeEnd) {
rangeForDeleteSet.add(subRange);
}
}
}
for (List<Integer> list : rangeForDeleteSet) {
rangeList.remove(list);
}
System.out.println(rangeList);
using range_t = pair<int, int>;
void removeSubranges(vector<range_t>& input) {
vector<range_t> output;
sort(input.begin(), input.end());
for (size_t prev = 0; prev < input.size(); ) {
size_t next = prev + 1;
while (next < input.size()) {
if (input[prev].first == input[next].first)
prev++;
else if (input[prev].second < input[next].first)
break;
next++;
}
output.push_back(input[prev]);
prev = next;
}
input = output;
}
using range_t = pair<int, int>;
void removeSubranges(vector<range_t>& input) {
vector<range_t> output;
sort(input.begin(), input.end());
for (size_t prev = 0; prev < input.size(); ) {
size_t next = prev + 1;
while (next < input.size()) {
if (input[prev].first == input[next].first)
prev++;
else if (input[prev].second < input[next].first)
break;
next++;
}
output.push_back(input[prev]);
prev = next;
}
input = output;
}
Here's a solution in JavaScript:
//
// Input: [[1,3], [5,7], [2,4], [6,8]]
// Output: [[1,4], [5,8]] (no specific order)
//
/**
* Do these two ranges overlap?
*
* @param {array} a
* @param {array} b
* @return {boolen}
*/
var overlaps = function (a, b) {
return a[0] >= b[0] && a[0] <= b[1] // a[lo] is in range of b
|| a[1] >= b[0] && a[1] <= b[1]; // a[hi] is in range of b
};
/**
* Merge two ranges, assuming overlap
*
* @param {array} a
* @param {array} b
* @return {array}
*/
var merge = function (a, b) {
return [Math.min(a[0], b[0]), Math.max(a[1], b[1])];
};
/**
* Merge a single range into a list of ranges
*
* @param {array[array]} list
* @param {array} range
* @param {array[array]}
*/
var mergeRange = function (list, range) {
for (var i = 0; i < list.length; i++) {
if (overlaps(list[i], range)) { // the range overlaps
var newRange = merge(list[i], range);
list.splice(i, 1);
return mergeRange(list, newRange); // recursive call
}
}
list.push(range); // the range doesn't overlap, so just add it to list
return list;
};
/**
* Merge a list of ranges into each other
*
* @param {array[array]} ranges
* @return {array[array]}
*/
var mergeRanges = function (ranges) {
return ranges.reduce(function (acc, curr) {
return mergeRange(acc, curr);
}, []);
};
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;
}
public class IntervalMerge {
public static void main(String[] args) {
List<Interval> list = new ArrayList<>();
Interval i1 = new Interval(2,6);
Interval i2 = new Interval(3,5);
Interval i3 = new Interval(7,21);
Interval i4 = new Interval(20,21);
list.add(i1);
list.add(i2);
list.add(i3);
list.add(i4);
IntervalMerge im = new IntervalMerge();
List<Interval> r = im.getOptimalIntervalList(list);
for (Interval interval : r) {
System.out.println(interval.s + " " + interval.e);
}
}
public List<Interval> getOptimalIntervalList(List<Interval> list) {
if (list == null || list.isEmpty()) {
return null;
}
Collections.sort(list);
List<Interval> r = new ArrayList<>();
int n = list.size();
boolean keep[] = new boolean[n];
Arrays.fill(keep, true);
Interval in1, in2;
int i = 1;
while (i < n) {
if (keep[i]) {
in1 = list.get(i);
in2 = list.get(i - 1);
if (in1.containsInterval(in2)) {
keep[i - 1] = false;
} else if (in2.containsInterval(in1)) {
keep[i] = false;
}
}
i++;
}
for (int j = 0; j < keep.length; j++) {
if (keep[j]) {
r.add(list.get(j));
}
}
return r;
}
}
class Interval implements Comparable<Interval> {
Integer s;
Integer e;
public Interval(int s, int e) {
super();
this.s = s;
this.e = e;
}
public boolean containsInterval(Interval i2) {
return (this.s <= i2.s && this.e >= i2.e);
}
@Override
public int compareTo(Interval o) {
return this.s.compareTo(o.s);
}
}
I was able to come up with a O(N^2) solution pretty quickly with no memory overhead. I'm having trouble coming up with anything that's much faster for all cases.
My basic algorithm:
1. Beginning at the 0th index and increasing by one, select an interval I --> (i, j)
2. Compare the selected interval to the intervals after it, J. If there is overlap between intervals, take the min(I.i, J.i) as the new start and the max(I.j, J.j) as the end. Update interval I. Delete interval J from the array. Continue comparing again from the index of I, plus 1.
3. If no interval in the array had an overlap, interval I is part of the solution set. Move on to the next index.
C++
struct Pair {
int i;
int j;
Pair(int a, int b)
{
i = a; j = b;
}
};
void remove(vector<Pair> &v, int index)
{
v[index].i = v[v.size() - 1].i;
v[index].j = v[v.size() - 1].j;
v.erase(v.end() - 1); // deleting from the end is O(1)
}
void combineRanges(vector<Pair> &input)
{
for(int i = 0; i < input.size(); i++)
{
bool done = true;
for(int j = i + 1; j < input.size(); j++)
{
// first range is entirely before second
if(input[i].j < input[j].i) continue;
// first range is entirely after second
if(input[i].i > input[j].j) continue;
// Otherwise, theres some sort of overlap
// take max of the J's and min of the I's
// to get the "new" range
done = false;
int newI = min(input[i].i, input[j].i);
int newJ = max(input[i].j, input[j].j);
// replace the ith item with this new range, delete the jth one
input[i].i = newI; input[i].j = newJ;
remove(input, j);
}
// repeat iteration with the new range at I to see if it can
// combine with any others
if(!done) i--;
}
}
int main()
{
vector<Pair> v;
v.push_back(Pair(6,8));
v.push_back(Pair(2,3));
v.push_back(Pair(4,7));
v.push_back(Pair(1,9));
printVector(v);
combineRanges(v);
printVector(v);
}
Output:
(6, 8) (2, 3) (4, 7) (1, 9)
(1, 9)
Sort the pair, and then check each one with its previous one, if its a subset of the previous one dont add, else if the previous one is subset of this one, remove the previous one, and then add this one (regardless).
- AbstractInstance October 19, 2015