Facebook Interview Question
Country: United States
Case #1:
S = {(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9), (9, 10), (10, 11)}
R = (1, 11);
while 10 x for 2 = 20. 2n => n
Case #2:
S = {(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10), (1, 11)}
R = (1, 11);
while 1 x for 10 = 10. n
Case #3:
S = {(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (6, 7), (6, 8), (6, 9), (6, 10), (6, 11)}
R = (1, 11);
1st while: 6 + 2nd while 4 = 10, n
Would you show me worst case sample?
@Ahmed Bassiouny The search part is O(n) alright! Try to look at it recursively and you'll see that it never visits a range more than twice always advancing forward because the target range's left point is shifting. And if kyduke updated maxIndex to last range that was filtered out, instead of maxIndex++, it would visit each range only once, it seams.
Very good algorithm.
@kyduke I used your awesome greedy tactics idea to reimplement the BFS part in my solution below. Now it does not queue children that end past the currently queued child. Effectively, it always queues only the one with max end.
For single run, your solution will be faster, because you only sort once nlogn, and then O(n) search, and I need to also construct the Inteval Tree.
But had the question asked to initialize once and run multiple queries then Interval Tree solution would have a potential to perform faster, because it is O(kLogn) k - size of output, and at most O(N) when all ranges end up in the output. (Am I correct with this analysis?)
in Python, nlog(n)
def small_set(l, R):
l.sort() # O(nlog(n))
if len(l) == 0 or l[0][0]>R[0]:
return []
if l[0][1] >= R[1]:
return [l[0]]
ret = []
start = R[0]
end = l[0][1]
greedy = l[0]
for inter in l[1:]: # O(n) loop
if inter[0] <= start:
if inter[1] > end: # find the interval starting before start with maximum reach
greedy = inter
end = inter[1]
if end >= R[1]:
ret.append(greedy)
return ret
else:
if inter[0] > end: # there is a hole
return []
ret.append(greedy) # push greedy and update start & end
start = end
greedy = inter
end = inter[1]
if end >= R[1]:
ret.append(greedy)
return ret
return []
I don't think we need to sort.
We have S consisting of a set of (ai, bi), where i = 1..N. We are to find the i which makes (a0-ai)+(bi-b0) the smallest, where R = (a0, b0). We can just go through the array, so it's O(N).
I think the above solution is way too complicated. Here is mine:
vector<pair<int, int> > S;
S.push_back(pair<int, int> (1,4));
S.push_back(pair<int, int> (30,40));
S.push_back(pair<int, int> (20,91));
S.push_back(pair<int, int> (8,10));
S.push_back(pair<int, int> (6,7));
S.push_back(pair<int, int> (3,9));
S.push_back(pair<int, int> (9,12));
S.push_back(pair<int, int> (11,14));
pair<int,int> result = pair<int, int> (3,13);
int start=result.first, end=result.first;
queue<pair<int, int> > q;
while(end<result.second)
{
start = end;
int k=0;
for(int i=0; i<S.size(); i++)
{
if(S[i].first<=start)
if(S[i].second>end)
{
end = S[i].second;
k=i;
}
}
q.push(S[k]);
}
while(!q.empty())
{
pair<int, int> temp = q.front();
cout<<temp.first<<","<<temp.second<<endl;
q.pop();
}
return 0;
What's the time complexity? it's kinda hard to follow your code, could you please explain?
Run Time: Exponential. (Exploring by Including and Excluding a current interval at any point)
bool myComparator(const pair<int, int>& a, const pair<int, int>& b)
{
if (a.first == b.first)
return a.second < b.second;
return a.first < b.first;
}
int coverage(vector<pair<int, int>>& v)
{
int range = 0;
for (auto& pair : v)
{
range += (pair.second - pair.first);
}
return range;
}
vector<pair<int, int>> findSmallestRangeIncludeExclude(vector<pair<int, int>>& v, pair<int, int> P, size_t index)
{
vector<pair<int, int>> include;
vector<pair<int, int>> exclude;
if (index >= v.size())
return include;
//If the current interval falls to left side of Given range then this interval cannot be included..
if (v[index].second < P.first)
{
exclude = findSmallestRangeIncludeExclude(v, P, index + 1);
}
else if (v[index].first > P.second) //If the current interval falls to Right side of Given range then Intervals from this index are of no interest.
{
return include;
}
else if (v[index].first <= P.first && v[index].second >= P.second) //Given Range is totally contained in this range.STOP exploring inclusions and explore only excluded sets
{
include.push_back(v[index]);
exclude = findSmallestRangeIncludeExclude(v, P, index + 1); //Explore indices on right if there is a smaller range..
}
else if (v[index].first <= P.first && v[index].second >= P.first) //Partial over lap..
{
include.push_back(v[index]);
auto temp = findSmallestRangeIncludeExclude(v, { v[index].second, P.second }, index + 1); //Include current range and explore for remaining.
if (temp.size() != 0)
{
include.insert(include.end(), temp.begin(), temp.end());
}
else //This path yielded in a no result..so just clear ou
{
include.clear();
}
exclude = findSmallestRangeIncludeExclude(v, P, index + 1);
}
//Check which is having the least coverage and return that..
if (include.size() == 0)
return exclude;
else if (exclude.size() == 0)
return include;
if (coverage(include) < coverage(exclude))
return include;
return exclude;
}
Expects a sorted range of Intervals based on starting time.
Call Routine:
sort(v.begin(), v.end(), myComparator);
auto temp = findSmallestRangeIncludeExclude(v, { 3, 13 }, 0);
for (auto& pair : temp)
{
cout << pair.first << " " << pair.second << endl;
}
Here's O(nlogn) solution based on Interval Tree and modified BFS.
The modified BFS is inspired by @kyduke greedy tactics, it does not add a child node if the currently stored node (the queued child) ends past new child, or replaces currently stored otherwise.
Input: list of 'ranges', target range 'r'
- First we add a dummy range [r.hi, max(tree_max, r.hi)] to ranges.
- Sort 'ranges' by 'lo'
- Build Balanced BST from sorted list
- From a dummy range [r.lo,r.lo] do BFS to reach [r.hi, max(tree_max, r.hi)]. (each node is one of the ranges in 'ranges' + the dummy, and edge is connected if 'node.hi' intersects another node which we determine by lookup in the interval tree.
It can be easily proven that any path from dummy start to end covers the whole input range. (by contradiction)
Now, since we use BFS, the output path represents one of the minimal subsets.
The complexity is dominated by sort and tree construction, but it would amortize in case this solution will be used for multiple queries, because dummy can be inserted and removed each time, and sorting/building tree is done only once. Then complexity of each query will be kLogn where k is the output set length (and at most N).
public class FindMinimalSubset {
private static final Logger logger = LoggerFactory.getLogger(FindMinimalSubset.class);
private IntervalNode bbstRoot = null;
public List<IntervalNode> getMinimalSet(List<IntervalNode> ranges, IntervalNode input) {
//sort ranges by lo and build balanced binary tree
Collections.sort(ranges);
//BST is used as interval tree, and it is balanced since the array was sorted
//prior to building the BST
buildIntervalT(ranges);
//insert the dummy end, it's 'hi' is max of input.hi and current max in the tree (that of root)
IntervalNode terminal = new IntervalNode(input.hi, Math.max(bbstRoot.max, input.hi));
insert(bbstRoot, terminal);
int left = input.lo;
int right = input.hi;
//do modified BFS filtering out ranges with smaller 'hi' than what was already found,
//from dummy start to dummy end and reconstruct path
//any path from start to end will contain the given range, and
//since it is a BFS, the path is minimal
IntervalNode bfsNode = doBfs(left, right, terminal);
//remove dummy end, in case need to be modified to initialize once and then multiple rins with different target range
//removeNode(terminal);
List<IntervalNode> path = reconstructPath(bfsNode);
return path;
}
//return path without last and first (which served as dummy start and end for bfs)
private List<IntervalNode> reconstructPath(IntervalNode bfsNode) {
if (bfsNode == null) {
return Collections.emptyList();
}
List<IntervalNode> ranges = new ArrayList<>();
IntervalNode parent = bfsNode.bfsParent;
while(parent != null && parent.bfsParent != null) {
ranges.add(parent);
parent = parent.bfsParent;
}
return ranges;
}
//do bfs starting with dummy start (lo,lo) and dummy end
private IntervalNode doBfs(int lo, int hi, IntervalNode terminalRange) {
Set<IntervalNode> visited = new HashSet<>();
//Queue<IntervalTNode> queue = new LinkedList<IntervalTNode>();
IntervalNode start = new IntervalNode(lo, lo);
visited.add(start);
IntervalNode currNode = start;
while (currNode != null) {
IntervalNode node = currNode;
currNode = null;
int x = node.hi;
//search for neighbors that intersect with 'hi' of this node in the interval tree
List<IntervalNode> containList = query(x);
if (containList != null) {
for (IntervalNode child : containList) {
if (child.equals(terminalRange)) {
child.bfsParent = node;
return child;
}
if (visited.contains(child) || child == node) {
continue;
}
visited.add(child);
if (currNode != null) {
if (currNode.hi < child.hi) {
currNode = child;
child.bfsParent = node;
}
} else {
currNode = child;
child.bfsParent = node;
}
}
}
}
return null;
}
private List<IntervalNode> query(int x) {
return query(bbstRoot, x);
}
private List<IntervalNode> query(IntervalNode root, int x) {
//usual interval tree query, as in wiki for example
//to find ranges that overlap the given point
}
private void buildIntervalT(List<IntervalNode> ranges) {
//the usual technique, can be found in wiki, using input[mid].lo as root key
bbstRoot = ...
}
private IntervalNode insert(IntervalNode root, IntervalNode newNode) {
//usual insert algorithm, can be found in wiki
}
public static class IntervalNode implements Comparable<IntervalNode>{
public int lo;
public int hi;
public IntervalNode bfsParent;
public IntervalNode left;
public IntervalNode right;
public int max = Integer.MIN_VALUE;
public IntervalNode(int lo, int hi) {
....
}
public boolean intersects(int x) {
return x>= lo && x<=hi;
}
@Override
public int compareTo(IntervalNode o) {
...
}
@Override
public int hashCode() {
...
}
@Override
public boolean equals(Object obj) {
...
}
}
}
public static class Range {
public int first;
public int second;
public Range(int first, int second) {
this.first = first;
this.second = second;
}
}
protected static class RangeComparator implements Comparator<Range> {
@Override
public int compare(Range r1, Range r2) {
if (r1 == r2) return 0;
if (r1.first > r2.first) return 1;
else return -1;
}
}
/*TARGET METHOD*/
public static List<Range> findOverlapRange(List<Range> givenRange, Range targetRange) {
List<Range> result = new ArrayList<Range>();
Collections.sort(givenRange, new RangeComparator());
int toFind = targetRange.first;
do {
Range foundRange = searchClosest(givenRange, toFind, 0, givenRange.size() - 1);
result.add(foundRange);
toFind = foundRange.second;
} while (toFind < targetRange.second);
return result;
//Complexity: )(nlogn)
}
protected static Range searchClosest(List<Range> givenRange, int element, int st, int end) {
int mid = st + (int) Math.floor((end - st) / 2);
if (st > end) return (end > -1 ? givenRange.get(end) : givenRange.get(st));
else if (givenRange.get(mid).first == element) return givenRange.get(mid);
else if (givenRange.get(mid).first < element) return searchClosest(givenRange, element, mid + 1, end);
else return searchClosest(givenRange, element, st, mid - 1);
}
public static class Range {
public int first;
public int second;
public Range(int first, int second) {
this.first = first;
this.second = second;
}
}
protected static class RangeComparator implements Comparator<Range> {
@Override
public int compare(Range r1, Range r2) {
if (r1 == r2) return 0;
if (r1.first > r2.first) return 1;
else return -1;
}
}
/*TARGET METHOD*/
public static List<Range> findOverlapRange(List<Range> givenRange, Range targetRange) {
List<Range> result = new ArrayList<Range>();
Collections.sort(givenRange, new RangeComparator());
int toFind = targetRange.first;
do {
Range foundRange = searchClosest(givenRange, toFind, 0, givenRange.size() - 1);
result.add(foundRange);
toFind = foundRange.second;
} while (toFind < targetRange.second);
return result;
//Complexity: )(nlogn)
}
protected static Range searchClosest(List<Range> givenRange, int element, int st, int end) {
int mid = st + (int) Math.floor((end - st) / 2);
if (st > end) return (end > -1 ? givenRange.get(end) : givenRange.get(st));
else if (givenRange.get(mid).first == element) return givenRange.get(mid);
else if (givenRange.get(mid).first < element) return searchClosest(givenRange, element, mid + 1, end);
else return searchClosest(givenRange, element, st, mid - 1);
}
int A[8][2] = {{1,3},{3,9},{6,7},{8,10},{9,12},{11,14},{20,91},{30,40}};
int R[2] = {3,13};
int i=-1;
int r2 = R[0];
while (A[i][1]<R[1])
{
while(A[i+1][0]<=r2) i++;
r2=A[i][1];
printf("%d %d\n",A[i][0], A[i][1]);
}
A best fit algorithm. This has one iteration through the given list of sets (o(n)) and some nLogn searches through the gaps array and candidates array.
public class SetCoverFB {
static class SetRange implements Comparable<SetRange> {
public final int start;
public final int end;
public SetRange(int start, int end) {
assert (start <= end);
this.start = start;
this.end = end;
}
@Override
public int compareTo(SetRange o) {
return Integer.compare(this.start, o.start);
}
@Override
public String toString() {
return "SetRange [start=" + start + ", end=" + end + "]";
}
}
public static void main(String[] args) {
final SetRange toCover = new SetRange(3, 13);
final List<SetRange> availSets = new ArrayList<>();
availSets.add(new SetRange(1, 4));
availSets.add(new SetRange(30, 40));
availSets.add(new SetRange(20, 91));
availSets.add(new SetRange(8, 10));
availSets.add(new SetRange(6, 7));
availSets.add(new SetRange(3, 9));
availSets.add(new SetRange(9, 12));
availSets.add(new SetRange(11, 14));
availSets.add(new SetRange(1, 4));
availSets.add(new SetRange(30, 40));
availSets.add(new SetRange(20, 91));
availSets.add(new SetRange(8, 10));
availSets.add(new SetRange(6, 7));
availSets.add(new SetRange(3, 9));
availSets.add(new SetRange(9, 12));
availSets.add(new SetRange(11, 14));
System.out.println(availSets);
// We find the min covering sets as follows:
// O(N)
// Iterate through the sets.
// Whenever we get a new set it is included If
// it overlaps / falls inside the toCover range (candidate)
// it actually covers a previously open area. (filler) OR
// it replaces two or more sets that were covering that area. (blanket
// set).
// Something to take care of: Ensure you check only the necessary
// cover instead of the range of the whole candidate / previous one.
// To make it easy, we maintain a list of gaps.
// We also maintain the current candidates ordered by start for easy
// comparison.
// gaps in the toCover range.
// THIS is a mutually exclusive set - no overlaps
Set<SetRange> gaps = new TreeSet<>();
gaps.add(toCover);
final Set<SetRange> candidates = new TreeSet<>();
for (SetRange candidate : availSets) {
System.out.println("candidate " + candidate);
// check for range
if (candidate.end < toCover.start) {
continue;
}
if (candidate.start > toCover.end) {
continue;
}
boolean isFiller = false;
// check for filler
for (SetRange gap : gaps) {
if (checkOverlap(candidate, gap)) {
isFiller = true;
break;
} else {
// since the set is ordered and has no overlaps, we can cut
// short if we are past our end
if (gap.end < candidate.start) {
assert (!isFiller);
break;
}
}
}
if (isFiller) {
Set<SetRange> newGaps = new TreeSet<>();
// adjust gaps.
for (SetRange gap : gaps) {
if (checkOverlap(candidate, gap)) {
if (!isCoveredBy(gap, candidate)) {
// there is a overlap - but no cover. So only
// partial cover.
if (gap.start < candidate.start) {
newGaps.add(new SetRange(gap.start,
candidate.start - 1));
if (candidate.end < gap.end) {
newGaps.add(new SetRange(candidate.end + 1,
gap.end));
}
} else if (gap.start == candidate.start) {
assert (gap.end > candidate.end); // no cover
newGaps.add(new SetRange(candidate.end + 1,
gap.end));
} else {// gap.start > candidate.start
assert (candidate.end < gap.end); // no cover
newGaps.add(new SetRange(candidate.end + 1,
gap.end));
}
}
} else {
newGaps.add(gap);
}
}
gaps = newGaps;
System.out.println("Gaps adjusted: " + gaps);
}
// check for blankets
// For this to blanket something else, it has to completely
// cover another set AND provide extra cover.
// It is also considered covering IF we don't cover only the useless
// portions.
Set<SetRange> toBeReplaced = new HashSet<>();
int lastValidCoverStart = toCover.start;
for (SetRange prevCandidate : candidates) {
if (prevCandidate.start > candidate.end) {
// our candidate is behind the current range - we can
// break out now since candidates is ordered by start.
if(! isFiller) {
candidate = null;// the candidate doesn't matter any more.
}
break;
}
final SetRange validCoverOfPrevCandidate = getValidCover(
lastValidCoverStart, toCover.end,
prevCandidate);
assert(validCoverOfPrevCandidate != null);
final SetRange validCoverOfCandidate = getValidCover(
lastValidCoverStart, toCover.end, candidate);
if(validCoverOfCandidate == null) {
// the previous candidate covers us - we are useless.
candidate = null;
break;
}
if (isCoveredBy(validCoverOfPrevCandidate,
validCoverOfCandidate)) {
toBeReplaced.add(prevCandidate);
}
lastValidCoverStart = prevCandidate.end;
}
if(candidate != null) {
candidates.removeAll(toBeReplaced);
candidates.add(candidate);
} else {
assert (!isFiller);
}
}
if (gaps.isEmpty()) {
System.out.println("For Range: " + toCover + ". Min cover: "
+ candidates);
} else {
System.out.println("For Range: " + toCover + ". Min cover: "
+ candidates + ". With gaps: " + gaps);
}
}
private static SetRange getValidCover(final int validStartPoint,
final int maxEndPoint, final SetRange candidate) {
// in case validStart is > candidate.end, candidate is useless
if(validStartPoint > candidate.end) {
return null;
}
final SetRange validCoverOfPrevCandidate = new SetRange(
candidate.start < validStartPoint ? validStartPoint
: candidate.start,
candidate.end > maxEndPoint ? maxEndPoint
: candidate.end);
return validCoverOfPrevCandidate;
}
static boolean isCoveredBy(SetRange toCheck, SetRange possibleCover) {
if (possibleCover.compareTo(toCheck) <= 0
&& possibleCover.end >= toCheck.end) {
return true;
}
return false;
}
static boolean checkOverlap(SetRange set1, SetRange set2) {
// completely outside
if ((set1.end < set2.start) || (set1.start > set2.end)) {
return false;
}
// some overlap
// set1 ends AFTER set2 starts
// AND set1 starts before set2 ends.
return true;
}
}
Sort based on start of the ranges (log n) then binary search based on start you got. The search criteria is to find a number with minimum distance from the start but not larger than it. When you found the starting range use the end number of that range to do this binary search again. Repeat until you passed given end number.
class RangeOverlap {
static void main(String... args) {
def ranges = [(1..4),(30..40),(20..91),(8..10),(6..7),(3..9),(9..12),(11..14),(3..5)]
def toOverlap = (3..13)
println findRangeSequence(ranges, toOverlap, [])
}
static List<IntRange> findRangeSequence(List<IntRange> ranges, IntRange toOverlap, List<IntRange> results) {
IntRange range = null
List<IntRange> currentRanges = ranges.findAll({
it.first() == toOverlap.first()
})
currentRanges.each {
if (!range) { range = it }
else if (it.size() > range.size()) { range = it }
}
if (range) {
results << range
if (!range.containsAll(toOverlap)) {
ranges.removeAll(currentRanges)
toOverlap = (range.last()..toOverlap.last())
findRangeSequence(ranges, toOverlap, results)
} else
results
}
else {
if (toOverlap.first() > 1) {
toOverlap = (toOverlap.first() - 1..toOverlap.last())
findRangeSequence(ranges, toOverlap, results)
}
else null
}
}
}
groovy
class RangeOverlap {
static void main(String... args) {
def ranges = [(1..4),(30..40),(20..91),(8..10),(6..7),(3..9),(9..12),(11..14),(3..5)]
def toOverlap = (3..13)
println findRangeSequence(ranges, toOverlap, [])
}
static List<IntRange> findRangeSequence(List<IntRange> ranges, IntRange toOverlap, List<IntRange> results) {
IntRange range = null
List<IntRange> currentRanges = ranges.findAll({
it.first() == toOverlap.first()
})
currentRanges.each {
if (!range) { range = it }
else if (it.size() > range.size()) { range = it }
}
if (range) {
results << range
if (!range.containsAll(toOverlap)) {
ranges.removeAll(currentRanges)
toOverlap = (range.last()..toOverlap.last())
findRangeSequence(ranges, toOverlap, results)
} else
results
}
else {
if (toOverlap.first() > 1) {
toOverlap = (toOverlap.first() - 1..toOverlap.last())
findRangeSequence(ranges, toOverlap, results)
}
else null
}
}
}
<?php
$S = [
range(1, 4),
range(30, 40),
range(20, 91),
range(8, 10),
range(6, 7),
range(3, 9),
range(9, 12),
range(11, 14)
];
$R = range(3, 13);
print_r(findMinSubset($S, $R));
/**
* @param array $S
* @param array $R
*
* @return array
*/
function findMinSubset(array $S, array $R)
{
$result = [];
while ($S && $R) {
$bestIndex = 0;
$bestResult = 0;
foreach ($S as $i => $s) {
$intersection = array_intersect($s, $R);
$cardinality = count($intersection);
if (0 === $cardinality) {
unset($S[$i]);
continue;
}
if ($cardinality > $bestResult) {
$bestResult = $cardinality;
$bestIndex = $i;
}
}
if (empty($S)) {
break;
}
$result[] = $S[$bestIndex];
$R = array_diff($R, $S[$bestIndex]);
unset($S[$bestIndex]);
}
return $result;
}
I have O(N*M) solution,
Where N is the number of pairs in the Set
and M is length of the given Range
in the given example N = 8 ; M = (13-3);
This is better than O(N log N) in the cases where N is scaled exorbitantly and M is a normal range like (3,13).
Its worse when the range is like (2,1000000).
Approach:
Make an array of integers spanning the given range. (here [3,4,...13]).
For each pair in the given set,
For each int in the array
if (Pair covers the integer && Pair is bigger than the existingPair that covers)
Mark as covered by Pair
Now the array of covered pairs is the answer.
The Code:
public class Ranger {
private static void doAction(int[] key,pair<Integer,Integer>[] ans,pair<Integer,Integer>[] set)
{
int i;
for(pair<Integer,Integer> s : set)
{
for(i=0;i<key.length;i++)
{
if(covers(key[i],s))
{
if((s.second-s.first)>=(ans[i].second-ans[i].first))
{
ans[i]=s;
}
}
}
}
}
private static boolean covers(int k, pair<Integer,Integer> p)
{
boolean a = false;
if(k>(p.first-1) && k<(p.second+1))
{
a = true;
}
return a;
}
public static void main(String args[])
{
String set = "(1,4);(30,40);(20,91);(8,10);(6,7);(3,9);(9,12);(11,14)";
pair<Integer,Integer> range = new pair(3,13);
pair<Integer,Integer>[] setArray;
String[] sArray = set.split(";");
setArray = new pair[sArray.length];
String[] vals;
int i =0;
for(String s : sArray)
{
s = s.substring(1, s.length()-1);
vals = s.split(",");
setArray[i]= new pair(Integer.parseInt(vals[0]),Integer.parseInt(vals[1]));
i++;
}
int[] hashArray = new int[range.second-range.first];
pair[] answer = new pair[range.second-range.first];
Arrays.fill(answer, new pair(0,0));
int f = range.first;
int j;
for(j=0;j<hashArray.length;j++,f++)
{
hashArray[j]=f;
}
doAction(hashArray,answer,setArray);
System.out.println(answer[0].first+","+answer[0].second);
for(j=1;j<answer.length;j++)
{
if(answer[j].first!=answer[j-1].first && answer[j].second!=answer[j-1].first)
System.out.println(answer[j].first+","+answer[j].second);
}
}
}
Time complexity is O(n log(n)), where n is the number of intervals.
def bins(v, x, key=lambda x: x):
""" returns the last index i such that x[i] <= v
-1 if it does not exist """
lo = 0
hi = len(x) - 1
if lo > hi:
return -1
if key(x[lo]) > key(v):
return -1
if key(x[hi]) <= key(v):
return hi
# invariant x[lo] <= v and v < x[hi]
while hi - lo > 1:
md = (lo + hi)/2
if key(x[md]) <= key(v):
lo = md
else:
hi = md
# (hi == lo or) hi == lo + 1
# and x[lo] <= v and v < x[hi]
return lo
def cover(il, i):
il = sorted(il, key = lambda x: x[1]) # radix sort
il = sorted(il, key = lambda x: x[0])
c = []
k = i
while k[0] < k[1]:
idx = bins(k, il, key = lambda x: x[0])
l = il[idx]
if idx == -1 or l[1] <= k[0]:
return []
c.append(l)
k = (l[1], k[1])
return c
print cover([(1,4), (30,40), (20,91), (8,10), (6,7), (3,9), (9,12), (11,14)], (3, 13))
This can be Solved using BFS to find shortest path. The graph will edge u-v if range u intersects range v i.e. u.start<=v.start<=u.end. The BFS is terminated when we find a range whose v.end >= target.end. Instead of actually creating the graph we can add all ranges into a TreeSet which is ordered based on the start value of the range. Then subset function can easily return all intersecting ranges for a given range.
Below is the implementation. The worst case time complexity in this case is O(nlogn) where n is number of ranges.:
class Solution {
private static class Range implements Comparable<Range>{
int start, end;
Range parent;
public Range(int st, int ed){
start = st;
end = ed;
parent = null;
}
// Order ranges by start
public int compareTo(Range that){
return start - that.start;
}
public String toString(){
return "("+start+","+end+")";
}
}
public static void getOverlappingRanges(int[][] ranges, int start, int end){
// Add ranges to balanced BST
TreeSet<Range> ordered_ranges = new TreeSet<Range>();
for(int i=0;i<ranges.length;i++)
ordered_ranges.add(new Range(ranges[i][0],ranges[i][1]));
Queue<Range> Q = new LinkedList<Range>();
HashSet<Range> visited = new HashSet<Range>();
Range target = new Range(start,end);
ArrayList<Range> overlappingRange = new ArrayList<Range>();
// Add possible start of overlapping ranges to Queue
for(Range begin : ordered_ranges.headSet(target, true)){
if(begin.end>=target.end){
overlappingRange.add(begin);
break;
}
else if(begin.end>=target.start){
Q.offer(begin);
visited.add(begin);
}
}
// No overlapping range found that overlaps start of target range or found single range that overlaps entire target range.
if(Q.isEmpty() || overlappingRange.size()>0){
if(overlappingRange.size()>0)
System.out.println(overlappingRange);
else
System.out.println("No Solution");
return;
}
Range curr = null;
// Perform BFS on set of overlapping ranges of curr range and terminate as soon as target range end is exceeded (Shortest Path)
// Also keep track of parent of each Range so that we can backtrack from last node to get the shortest path
while(!Q.isEmpty()){
curr = Q.poll();
if(curr.end>=target.end)
break;
for(Range next : ordered_ranges.subSet(curr, true, new Range(curr.end,-1), true)){
if(!visited.contains(next)){
next.parent = curr;
Q.offer(next);
visited.add(next);
}
}
}
if(Q.isEmpty() && curr.end<target.end){
System.out.println("No Solution");
return;
}
// Backtrack to get shortest path
while(curr!=null){
overlappingRange.add(curr);
curr = curr.parent;
}
Collections.sort(overlappingRange);
System.out.println(overlappingRange);
}
public static void main(String[] args) {
int[][] ranges = {{1,4},{30,40},{20,91},{8,10},{6,7},{3,9},{9,12},{11,14}};
getOverlappingRanges(ranges,3,10);
}
}
This can be solved using BFS to find shortest path in a graph. The graph will contain an edge u-v when range v intersects range u such that u.start<=v.start<=u.end. We have found the soln when we encounter a range v such that v.end>=target.end.
Instead of actually constructing the graph we can simply add all ranges to a Treeset that is ordered by the start of the range. Then treeset headSet and subset functions can easily return adjacent/intersecting nodes for a range. Note that instead of having one node that starts the BFS here we will need to add all nodes which intersect with start of target range. Below is the implementation based on this logic. The worst case time complexity will be O(nlogn) where n is number of ranges:
class Solution {
private static class Range implements Comparable<Range>{
int start, end;
Range parent;
public Range(int st, int ed){
start = st;
end = ed;
parent = null;
}
// Order ranges by start
public int compareTo(Range that){
return start - that.start;
}
public String toString(){
return "("+start+","+end+")";
}
}
public static void getOverlappingRanges(int[][] ranges, int start, int end){
// Add ranges to balanced BST
TreeSet<Range> ordered_ranges = new TreeSet<Range>();
for(int i=0;i<ranges.length;i++)
ordered_ranges.add(new Range(ranges[i][0],ranges[i][1]));
Queue<Range> Q = new LinkedList<Range>();
HashSet<Range> visited = new HashSet<Range>();
Range target = new Range(start,end);
ArrayList<Range> overlappingRange = new ArrayList<Range>();
// Add possible start of overlapping ranges to Queue
for(Range begin : ordered_ranges.headSet(target, true)){
if(begin.end>=target.end){
overlappingRange.add(begin);
break;
}
else if(begin.end>=target.start){
Q.offer(begin);
visited.add(begin);
}
}
// No overlapping range found that overlaps start of target range or found single range that overlaps entire target range.
if(Q.isEmpty() || overlappingRange.size()>0){
if(overlappingRange.size()>0)
System.out.println(overlappingRange);
else
System.out.println("No Solution");
return;
}
Range curr = null;
// Perform BFS on set of overlapping ranges of curr range and terminate as soon as target range end is exceeded (Shortest Path)
// Also keep track of parent of each Range so that we can backtrack from last node to get the shortest path
while(!Q.isEmpty()){
curr = Q.poll();
if(curr.end>=target.end)
break;
for(Range next : ordered_ranges.subSet(curr, true, new Range(curr.end,-1), true)){
if(!visited.contains(next)){
next.parent = curr;
Q.offer(next);
visited.add(next);
}
}
}
if(Q.isEmpty() && curr.end<target.end){
System.out.println("No Solution");
return;
}
// Backtrack to get shortest path
while(curr!=null){
overlappingRange.add(curr);
curr = curr.parent;
}
Collections.sort(overlappingRange);
System.out.println(overlappingRange);
}
public static void main(String[] args) {
int[][] ranges = {{1,4},{30,40},{20,91},{8,10},{6,7},{3,9},{9,12},{11,14}};
getOverlappingRanges(ranges,3,10);
}
}
This should run in O(nlogn) time. The bottleneck is in sorting the array. The rest of the algorithm runs in O(n).
import java.util.*;
class SmallestRangingSet {
static class Interval implements Comparable<Interval>{
Integer min;
Integer max;
public Interval(int min, int max) {
this.min = min;
this.max = max;
}
boolean intersects(int num) {
return (min <= num && max >= num);
}
//Overrides the compareTo method so it will be sorted
//in order relative to the min value
@Override
public int compareTo(Interval obj) {
if (min > obj.min) return 1;
else if (min < obj.min) return -1;
else return 0;
}
}
public static Set<Interval> smallestIntervalSet(Interval[] set, Interval target) {
//Bottle neck is here. The array is sorted, giving this algorithm O(nlogn) time
Arrays.sort(set);
//Create a set to store our ranges in
Set<Interval> smallSet = new HashSet<Interval>();
//Create a variable to keep track of the most optimal range, relative
//to the range before it, at all times.
Interval bestOfCurr = null;
//Keep track of the specific number that any given range will need to
//intersect with. Initialize it to the target-min-value.
int currBestNum = target.min;
//Go through each element in our sorted array.
for (int i = 0; i < set.length; i++) {
Interval currInterval = set[i];
//If we have already passed our target max, break.
if (currBestNum >= target.max)
break;
//Otherwise, if the current interval intersects with
//our currBestNum
if (currInterval.intersects(currBestNum)) {
//If the current interval, which intersects currBestNum
//has a greater max, then our current bestOfCurr
//Update bestOfCurr to be equal to currInterval.
if (bestOfCurr == null || currInterval.max >= bestOfCurr.max) {
bestOfCurr = currInterval;
}
}
//If our range does not intersect, we can assume that the most recently
//updated bestOfCurr is probably the most optimal new range to add to
//our set. However, if bestOfCurr is null, it means it was never updated,
//because there is a gap somewhere when trying to fill our target range.
//So we must check for null first.
else if (bestOfCurr != null) {
//If it's not null, add bestOfCurr to our set
smallSet.add(bestOfCurr);
//Update currBestNum to look for intervals that
//intersect with bestOfCurr.max
currBestNum = bestOfCurr.max;
//This line is here because without it, it actually skips over
//the next Interval, which is problematic if your sorted array
//has two optimal Intervals next to eachother.
i--;
//set bestOfCurr to null, so that it won't run
//this section of code twice on the same Interval.
bestOfCurr = null;
}
}
//Now we should just make sure that we have in fact covered the entire
//target range. If we haven't, then we are going to return an empty list.
if (currBestNum < target.max)
smallSet.clear();
return smallSet;
}
public static void main(String[] args) {
//{(1, 4), (30, 40), (20, 91) ,(8, 10), (6, 7), (3, 9), (9, 12), (11, 14)}
Interval[] interv = {
new Interval(1, 4),
new Interval(30, 40),
new Interval(20, 91),
new Interval(8, 10),
new Interval(6, 7),
new Interval(3, 9),
new Interval(9, 12),
new Interval(11, 14)
};
Set<Interval> newSet = smallestIntervalSet(interv, new Interval(3,14));
for (Interval intrv : newSet) {
System.out.print("(" + intrv.min + ", " + intrv.max + ") ");
}
}
}
Either the question is wrong or the requirements have to be different given the question
(e.g. S = {(1, 4), (30, 40), (20, 91) ,(8, 10), (6, 7), (3, 9), (9, 12), (11, 14)}. and target 3,13.
Minimum overlapping intervals would be (9,12) and (11,14) and not (3,9), (9,12) and (11,14) because (3,9) does not overlap (11,14) in anyways.
So the question should be find minimum overlapping intervals that fulfills the condition that adjacents overlap and not otherwise.
c++, greedy, O(n log n)
sort: O(n log n), greedy: O(n)
- kyduke November 02, 2015struct Compare { bool operator() (const pair<int, int>& a, const pair<int, int>& b) { if (a.first == b.first) return a.second < b.second; return a.first < b.first; } }; vector<pair<int, int>> smallestSetOfRanges(vector<pair<int, int>>& ranges, pair<int, int> R) { vector<pair<int, int>> result; int target, i, maxTarget, maxIndex; bool match; if (R.first == R.second) { for (i = 0; i < ranges.size(); i++) { if (ranges[i].first <= R.first && ranges[i].second >= R.second) { result.push_back(ranges[i]); break; } } return result; } sort(ranges.begin(), ranges.end(), Compare()); target = R.first; maxIndex = 0; while (target < R.second) { match = false; maxTarget = target; for (i = maxIndex; i < ranges.size(); i++) { if (ranges[i].first <= target && ranges[i].second >= maxTarget) { match = true; maxTarget = ranges[i].second; maxIndex = i; } else if (ranges[i].first > target) { break; } } if (match == false) { result.clear(); break; } result.push_back(ranges[maxIndex]); target = maxTarget; maxIndex++; } return result; }