Google Interview Question
SDE1sCountry: United States
1. Consider all intervals which start before the target start time
2. Among those pick the interval with max end time
3. Update the target start time to the previous max end time and repeat
public static int minimumMerge(Interval[] intervals, Interval target) {
int result = 0;
Arrays.sort(intervals);
int targetStart = target.start;
int maxEndtime = Integer.MIN_VALUE;
int mergedIntervals = 0;
int i=0;
while (i < intervals.length) {
if (intervals[i].start <= targetStart) {
maxEndtime = Math.max(maxEndtime, intervals[i].end);
i++;
} else {
targetStart = maxEndtime+1;
mergedIntervals++;
}
}
if (maxEndtime >= target.end) return ++mergedIntervals;
return 0;
}
public static class Interval implements Comparable<Interval>{
int start;
int end;
Interval() { start = 0; end = 0; }
Interval(int s, int e) { start = s; end = e; }
public int compareTo(Interval i) {
return start-i.start;
}
}
public static int findMinInterval(Interval[] intervals, Interval target){
if(intervals.length==0)
return Integer.MAX_VALUE;
int min=Integer.MAX_VALUE;
Arrays.sort(intervals,new Comparator<Interval>(){
public int compare(Interval a,Interval b){
return a.start-b.start;
}
});
for(int i=0;i<intervals.length;i++){
if(intervals[i].start>target.start)
break;
if(intervals[i].start<=target.start && intervals[i].end>= target.end ){
min=1;
break;
}
int temp_min=1;
Interval curInterval= intervals[i];
Interval prevInterval= null;
for(int j=i+1;j<intervals.length;j++){
if(intervals[j].start<= curInterval.end && intervals[j].end>= target.end){
if(prevInterval==null || (prevInterval!=null && intervals[j].start>prevInterval.end))
temp_min+=1;
if(min>temp_min)
min=temp_min;
break;
}
else if(intervals[j].start> curInterval.start && intervals[j].start<=curInterval.end && intervals[j].end> curInterval.end){
if(prevInterval==null || (prevInterval!=null && intervals[j].start>prevInterval.end)){
temp_min+=1;
prevInterval= curInterval;
}
curInterval=intervals[j];
}
}
}
return min;
}
Recursive approach in Scala
object CoverIntervals {
case class Interval(start: Int, end: Int)
def findOneCoveringInterval(intervals: Set[Interval], target: Interval): Boolean =
intervals.exists(interval => interval.start <= target.start && interval.end >= target.end)
def partlyCovers(el: Interval, target: Interval): Boolean =
(el.start < target.start && el.end >= target.start) || (el.start < target.end && el.end >= target.end)
def cutTarget(interval: Interval, target: Interval): Interval =
if (interval.start < target.start && interval.end >= target.start)
Interval(interval.end, target.end)
else if (interval.start < target.end && interval.end >= target.end)
Interval(target.start, interval.start)
else throw new RuntimeException("unexpected arg: " + interval + " " + target)
def findMinInterval(intervals :Set[Interval], target: Interval): Option[Int] = {
if (findOneCoveringInterval(intervals, target))
Some(1)
else {
val partlyCovered = intervals.filter(el => partlyCovers(el, target))
if (partlyCovered.size == 0)
Option.empty
else {
val res = for {
interval <- partlyCovered
number <- findMinInterval(intervals - interval, cutTarget(interval, target))
} yield (number)
if (res.isEmpty)
Option.empty
else
Option(res.min + 1)
}
}
}
}
def find_min_intervals(intervals, target):
intervals.sort()
ct = target[0]
i = 0
max_step = 0
res = 0
while i < len(intervals):
while i < len(intervals) and intervals[i][0] <= ct:
max_step = max(max_step, intervals[i][1])
i += 1
ct = max_step
res += 1
return res
print find_min_intervals([[-1, 9], [1, 10], [0, 3], [9,10], [3, 14], [2, 9], [10, 16]], [2,15])
I think this method should be right, basical idea is using TreeMap, and the time complexity is O(nLog(n)):
public static int minMerge(List<Interval> intervals,Interval target){
TreeMap<Integer,Integer> treemap = new TreeMap<>();
for(int i=0;i<intervals.size();i++){
Interval temp = intervals.get(i);
if(treemap.containsKey(temp.start)){
treemap.put(temp.start,Math.max(temp.end,treemap.get(temp.start)));
}else{
treemap.put(temp.start,temp.end);
}
}
int count = 0;
int cur_end = target.start;
while(treemap.size()!=0){
count++;
Integer next_start = treemap.floorKey(cur_end);
if(next_start==null){
return 0;
}
Integer next_end = treemap.get(next_start);
treemap.remove(next_start);
while(!treemap.isEmpty()){
next_start = treemap.floorKey(cur_end);
if(next_start==null){
break;
}
next_end = Math.max(next_end,treemap.get(next_start));
treemap.remove(next_start);
}
if(next_end>=target.end){
return count;
}
cur_end = next_end;
}
return 0;
}
Copy pasting here:
here's my explanation and well-commented code, hope it will help :)
Greedy: choose furthest range
0. sort by start, upon same, by end(not necessary)
find eligible intervals for start: base start = target.start
definition of eligible intervals: x is eligible if x.start <= start && x.end > start
special case: if the earliest start > start, no ans, break!!!
Among all eligible intervals, choose the one that has the furthest range
count++;
if(furthest range >= target.end) -> ans found
update start to furthest range
repeat the iteration
public static int leastMerge(List<Interval> list, Interval interval) {
//0. sort by start
Collections.sort(list, (o1, o2) -> o1.start - o2.start);
int i = 0;
int start = interval.start;
int count = 0;
while (i < list.size()) {
//special case, no way to cover
if (list.get(i).start > start) {
break;
}
int furthest = Integer.MIN_VALUE;
//1. find eligible intervals
while (i < list.size() && list.get(i).start <= start) {
if (list.get(i).end > start) { //eligible
//2. choose the one that has the furthest range
if (list.get(i).end > furthest) {
furthest = list.get(i).end;
}
}
i++;
}
count++;
if (furthest >= interval.end) return count;
//3. update start to furthest range
start = furthest;
}
return 0;
}
- havefun March 11, 2017