Facebook Interview Question
Software EngineersCountry: United States
Its very simple, the code works.
Just put those interval on a line and see. U'll understand
It is the overlapping intervals questions with a small modification.
If you have seen at least one such interval question - all of them are easy, if you have never seen them - they will be impossible to solve.
function intervalTotalRange(intervals) {
var starts = intervals.map(i => i.start).sort((a, b) => a - b);
var ends = intervals.map(i => i.end).sort((a, b) => a - b);
var totalRange = 0;
var currentStart = 0;
var currentCount = 0;
for (var i = 0, j = 0; i < starts.length && j < ends.length;) {
if (starts[i] <= ends[j]) {
// start point
if (currentCount == 0) {
currentStart = starts[i];
}
currentCount++;
i++;
} else {
// finish point
currentCount--;
if (currentCount == 0) {
totalRange += (ends[j] - currentStart);
}
j++;
}
}
totalRange += (ends[ends.length - 1] - currentStart);
return totalRange;
}
This doesn't work for - intervalTotalRange([[1,10],[5,8],[7,9]])
The total overlap duration is from 5-9. Which is 4 hours. But the function above gives 9 hours.
O(n * logn) complexity as this is a classic overlapping intervals problem that requires sorting start and end points.
function intervalTotalRange(intervals) {
var starts = intervals.map(i => i.start).sort((a, b) => a - b);
var ends = intervals.map(i => i.end).sort((a, b) => a - b);
var totalRange = 0;
var currentStart = 0;
var currentCount = 0;
for (var i = 0, j = 0; i < starts.length && j < ends.length;) {
if (starts[i] <= ends[j]) {
// start point
if (currentCount == 0) {
currentStart = starts[i];
}
currentCount++;
i++;
} else {
// finish point
currentCount--;
if (currentCount == 0) {
totalRange += (ends[j] - currentStart);
}
j++;
}
}
totalRange += (ends[ends.length - 1] - currentStart);
return totalRange;
}
A simpler solution is possible if intervals are always given by ordered pair integers and their total range is not too large.
def coverage(intervals):
mina = 2**64
maxb = -2**64
for interval in intervals:
mina = min(mina, interval[0])
maxb = max(maxb, interval[1])
mask = [0]*(maxb - mina)
for interval in intervals:
for i in range(interval[0], interval[1]):
mask[i-mina] = 1
return sum(mask)
Too naive?
This is a nice solution if the total range of the intervals is small enough. Note that in the worst case, all entries in the mask must be marked True (or 1 in your case), which takes O(total range) time, which is exponential in the input size (as the interval points are encoded in binary).
public static void main(String[] args)
{
ArrayList<List<Integer>> rangeList = new ArrayList<>();
rangeList.add(Arrays.asList(1,4));
rangeList.add(Arrays.asList(6,8));
rangeList.add(Arrays.asList(2,4));
rangeList.add(Arrays.asList(7,9));
rangeList.add(Arrays.asList(10,15));
ArrayList<List<Integer>> result = mergeRange(rangeList);
System.out.println(sumRange(result));
}
public static int sumRange(ArrayList<List<Integer>> list) {
int sum = 0;
for(int i=0; i<list.size(); i++) {
sum = sum + (list.get(i).get(1) - list.get(i).get(0));
}
return sum;
}
public static ArrayList<List<Integer>> mergeRange(ArrayList<List<Integer>> rangeList)
{
if(rangeList.isEmpty()) return rangeList;
ArrayList<List<Integer>> result = new ArrayList<>();
Collections.sort(rangeList, new Comparator<List<Integer>>() {
@Override
public int compare(List<Integer> range1, List<Integer> range2)
{
return range1.get(0) - range2.get(0);
}
});
List<Integer> first = rangeList.get(0);
int start = first.get(0);
int end = first.get(1);
for(int i=0; i<rangeList.size(); i++)
{
List<Integer> current = rangeList.get(i);
if(current.get(0) <= end)
{
end = Math.max(current.get(1), end);
}
else
{
ArrayList<Integer> temp = new ArrayList<>();
temp.add(start);
temp.add(end);
result.add(temp);
start = current.get(0);
end = current.get(1);
}
}
ArrayList<Integer> temp = new ArrayList<>();
temp.add(start);
temp.add(end);
result.add(temp);
return result;
}
public static void main(String[] args)
{
ArrayList<List<Integer>> rangeList = new ArrayList<>();
rangeList.add(Arrays.asList(1,4));
rangeList.add(Arrays.asList(6,8));
rangeList.add(Arrays.asList(2,4));
rangeList.add(Arrays.asList(7,9));
rangeList.add(Arrays.asList(10,15));
ArrayList<List<Integer>> result = mergeRange(rangeList);
System.out.println(sumRange(result));
}
public static int sumRange(ArrayList<List<Integer>> list) {
int sum = 0;
for(int i=0; i<list.size(); i++) {
sum = sum + (list.get(i).get(1) - list.get(i).get(0));
}
return sum;
}
public static ArrayList<List<Integer>> mergeRange(ArrayList<List<Integer>> rangeList)
{
if(rangeList.isEmpty()) return rangeList;
ArrayList<List<Integer>> result = new ArrayList<>();
Collections.sort(rangeList, new Comparator<List<Integer>>() {
@Override
public int compare(List<Integer> range1, List<Integer> range2)
{
return range1.get(0) - range2.get(0);
}
});
List<Integer> first = rangeList.get(0);
int start = first.get(0);
int end = first.get(1);
for(int i=0; i<rangeList.size(); i++)
{
List<Integer> current = rangeList.get(i);
if(current.get(0) <= end)
{
end = Math.max(current.get(1), end);
}
else
{
ArrayList<Integer> temp = new ArrayList<>();
temp.add(start);
temp.add(end);
result.add(temp);
start = current.get(0);
end = current.get(1);
}
}
ArrayList<Integer> temp = new ArrayList<>();
temp.add(start);
temp.add(end);
result.add(temp);
return result;
}
public static void main(String[] args)
{
ArrayList<List<Integer>> rangeList = new ArrayList<>();
rangeList.add(Arrays.asList(1,4));
rangeList.add(Arrays.asList(6,8));
rangeList.add(Arrays.asList(2,4));
rangeList.add(Arrays.asList(7,9));
rangeList.add(Arrays.asList(10,15));
ArrayList<List<Integer>> result = mergeRange(rangeList);
System.out.println(sumRange(result));
}
public static int sumRange(ArrayList<List<Integer>> list) {
int sum = 0;
for(int i=0; i<list.size(); i++) {
sum = sum + (list.get(i).get(1) - list.get(i).get(0));
}
return sum;
}
public static ArrayList<List<Integer>> mergeRange(ArrayList<List<Integer>> rangeList)
{
if(rangeList.isEmpty()) return rangeList;
ArrayList<List<Integer>> result = new ArrayList<>();
Collections.sort(rangeList, new Comparator<List<Integer>>() {
@Override
public int compare(List<Integer> range1, List<Integer> range2)
{
return range1.get(0) - range2.get(0);
}
});
List<Integer> first = rangeList.get(0);
int start = first.get(0);
int end = first.get(1);
for(int i=0; i<rangeList.size(); i++)
{
List<Integer> current = rangeList.get(i);
if(current.get(0) <= end)
{
end = Math.max(current.get(1), end);
}
else
{
ArrayList<Integer> temp = new ArrayList<>();
temp.add(start);
temp.add(end);
result.add(temp);
start = current.get(0);
end = current.get(1);
}
}
ArrayList<Integer> temp = new ArrayList<>();
temp.add(start);
temp.add(end);
result.add(temp);
return result;
}
Functional approach using Scala:
object MergeCountIntervals {
def main(args: Array[String]): Unit = {
println(mergeSegments(Array(Array(1,4), Array(2,3))))
println(mergeSegments(Array(Array(4,6), Array(1,2))))
println(mergeSegments(Array(Array(1,4), Array(6,8), Array(2,4), Array(7,9), Array(10,15))))
}
def mergeSegments(segments: Array[Array[Int]]): Int = {
if (segments == null || segments.length == 0) return 0
val list = List.empty[Array[Int]]
val merged = segments.sortWith(_(0) < _(0)).foldLeft(list)((seq, s) =>
if (seq.isEmpty || seq.last(1) < s(0)) {
seq :+ s
} else {
val last = seq.last
seq.dropRight(1) :+ Array(last(0), Math.max(last(1), s(1)))
}
)
merged.foldLeft(0)((acc, x) => acc + x(1) - x(0))
}
}
// output:
/*
3
3
11
*/
My solution in Java:
public static void main(String[] args) {
List<Pair<Integer, Integer>> intervals = new ArrayList<>();
intervals.add(new Pair<>(1, 4));
intervals.add(new Pair<>(6, 8));
intervals.add(new Pair<>(2, 4));
intervals.add(new Pair<>(7, 9));
intervals.add(new Pair<>(10, 15));
System.out.println(totalTime(intervals));
}
private static int totalTime(List<Pair<Integer, Integer>> intervals) {
intervals.sort((left, right) -> left.first.compareTo(right.first));
if (intervals.isEmpty()) {
return 0;
}
if (intervals.size() == 1) {
return intervals.get(0).second - intervals.get(0).first;
}
int sum = 0;
Pair<Integer, Integer> temp = intervals.get(0);
for (int i = 1; i < intervals.size(); i++) {
if (temp.second >= intervals.get(i).first) {
temp = new Pair<>(temp.first, Math.max(temp.second, intervals.get(i).second));
continue;
}
sum += temp.second - temp.first;
temp = intervals.get(i);
}
sum += temp.second - temp.first;
return sum;
}
Improved solution in python that I stress test it against my first naive one.
def do_overlap(interval, last):
imin = interval[0]
imax = interval[1]
lmin = last[0]
lmax = last[1]
return imax >= lmin and lmax >= imin
def merge(interval, last):
# This is why a merger needs to be mutable
last[0] = min(last[0], interval[0])
last[1] = max(last[1], interval[1])
def sum_intervals(intervals):
result = 0
for interval in intervals:
result += interval[1] - interval[0]
return result
def coverage(intervals):
# Sort using interval mins as key
intervals.sort()
# Collection of non-overlaping intervals
# Each merger needs to be mutable
mergers = None
for interval in intervals:
if mergers is None:
mergers = [list(interval)]
continue
# Correctness proof:
# Show that checking last merger is enough
last = mergers[-1]
if do_overlap(interval, last):
merge(interval, last)
else:
mergers.append(list(interval))
return sum_intervals(mergers)
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Sample {
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<Interval> input = new ArrayList();
input.add(new Interval(0,1));
input.add(new Interval(2,6));
input.add(new Interval(3,8));
input.add(new Interval(1,4));
input.add(new Interval(10,14));
Collections.sort(input,new SortByStart());
ArrayList<Interval> result = new ArrayList<>();
for(int i = 0 ; i < input.size() ; i++){
if(result.isEmpty()){
result.add(new Interval(input.get(i).start,input.get(i).end));
}else{
if(input.get(i).start > result.get(result.size()-1).end){
result.add(new Interval(input.get(i).start,input.get(i).end));
} else if(input.get(i).start <= result.get(result.size()-1).end && input.get(i).end > result.get(result.size()-1).end){
result.get(result.size()-1).end = input.get(i).end;
}else if(input.get(i).start < result.get(result.size()-1).end && input.get(i).end <= result.get(result.size()-1).end){
// Discard interval
}
}
}
int totalTime = 0;
for(int i = 0 ; i < result.size() ; i++){
//System.out.println(result.get(i).start+" "+result.get(i).end);
totalTime += result.get(i).end - result.get(i).start;
}
System.out.println("Total Time Interval "+totalTime);
}
public static class SortByStart implements Comparator<Interval>{
@Override
public int compare(Interval o1, Interval o2) {
return o1.start - o2.start;
}
}
public static class Interval {
public Interval(int start, int end){
this.start = start;
this.end = end;
}
int start;
int end;
}
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Sample {
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<Interval> input = new ArrayList();
input.add(new Interval(0,1));
input.add(new Interval(2,6));
input.add(new Interval(3,8));
input.add(new Interval(1,4));
input.add(new Interval(10,14));
Collections.sort(input,new SortByStart());
ArrayList<Interval> result = new ArrayList<>();
for(int i = 0 ; i < input.size() ; i++){
if(result.isEmpty()){
result.add(new Interval(input.get(i).start,input.get(i).end));
}else{
if(input.get(i).start > result.get(result.size()-1).end){
result.add(new Interval(input.get(i).start,input.get(i).end));
} else if(input.get(i).start <= result.get(result.size()-1).end && input.get(i).end > result.get(result.size()-1).end){
result.get(result.size()-1).end = input.get(i).end;
}else if(input.get(i).start < result.get(result.size()-1).end && input.get(i).end <= result.get(result.size()-1).end){
// Discard interval
}
}
}
int totalTime = 0;
for(int i = 0 ; i < result.size() ; i++){
//System.out.println(result.get(i).start+" "+result.get(i).end);
totalTime += result.get(i).end - result.get(i).start;
}
System.out.println("Total Time Interval "+totalTime);
}
public static class SortByStart implements Comparator<Interval>{
@Override
public int compare(Interval o1, Interval o2) {
return o1.start - o2.start;
}
}
public static class Interval {
public Interval(int start, int end){
this.start = start;
this.end = end;
}
int start;
int end;
}
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Sample {
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<Interval> input = new ArrayList();
input.add(new Interval(0,1));
input.add(new Interval(2,6));
input.add(new Interval(3,8));
input.add(new Interval(1,4));
input.add(new Interval(10,14));
Collections.sort(input,new SortByStart());
ArrayList<Interval> result = new ArrayList<>();
for(int i = 0 ; i < input.size() ; i++){
if(result.isEmpty()){
result.add(new Interval(input.get(i).start,input.get(i).end));
}else{
if(input.get(i).start > result.get(result.size()-1).end){
result.add(new Interval(input.get(i).start,input.get(i).end));
} else if(input.get(i).start <= result.get(result.size()-1).end && input.get(i).end > result.get(result.size()-1).end){
result.get(result.size()-1).end = input.get(i).end;
}else if(input.get(i).start < result.get(result.size()-1).end && input.get(i).end <= result.get(result.size()-1).end){
// Discard interval
}
}
}
int totalTime = 0;
for(int i = 0 ; i < result.size() ; i++){
//System.out.println(result.get(i).start+" "+result.get(i).end);
totalTime += result.get(i).end - result.get(i).start;
}
System.out.println("Total Time Interval "+totalTime);
}
public static class SortByStart implements Comparator<Interval>{
@Override
public int compare(Interval o1, Interval o2) {
return o1.start - o2.start;
}
}
public static class Interval {
public Interval(int start, int end){
this.start = start;
this.end = end;
}
int start;
int end;
}
}
public static int calc(int[][] intervals) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int[] is : intervals) {
if (!map.containsKey(is[0]) || map.get(is[0]) < is[0])
map.put(is[0], is[1]);
}
List<Object> keyList = Arrays.asList(map.keySet().toArray());
int start = (Integer) keyList.get(0);
int end = map.get(start);
int diff = 0;
for (int i = 1; i < keyList.size(); i++) {
int c = (Integer) keyList.get(i);
int d = map.get(c);
if (end < c)
diff += c - end;
end = Math.max(end, d);
}
return end - start - diff;
}
My rather specific solution. I need more practice, but went with the simple to construct/understand brute force approach.
int timeElapsed(int[][] timeIntervals)
{
int elapsedTime = 0;
int tempEnd = 0;
int tempBegin = 0;
// Sort Array by start time
Arrays.sort(timeIntervals,Comparator.comparing((int [] arr) -> arr[0]));
for(int i = 0; i < timeIntervals.length; i++)
{
tempBegin = timeIntervals[i][0];
for(int j = i+1; j < timeIntervals.length; j++)
{
if(timeIntervals[i][1] <= timeIntervals[j][1]
&& timeIntervals[i][1] >= timeIntervals[j][0])
{
i = j;
break;
}
}
if(tempEnd < timeIntervals[i][1])
{
tempEnd = timeIntervals[i][1];
elapsedTime += tempEnd - tempBegin;
}
}
System.out.println("Time elapsed " + elapsedTime);
return elapsedTime;
}
I used this task to finally start practicing Python.
At least amount of lines of code is small enough to make me think that solution is quite simple :-)
{pairs=[(1,4),(6,8),(2,4),(7,9),(10,15)]
hours = set()
for first,last in pairs:
i = first
while i<=last:
print(i)
hours.add(i)
i+=1
print("total hours=",len(hours))}
This is my first code in Python. At least I like simplicity and because of lack of practice in Python I have very small idea on efficiency of it.
pairs=[(1,4),(6,8),(2,4),(7,9),(10,15)]
hours = set()
for first,last in pairs:
i = first
while i<=last:
print(i)
hours.add(i)
i+=1
print("total hours=",len(hours))
This can handle real time interval addition
//Reak time time interval Parsing.
using System;
using System.Collections.Generic;
public class Solution
{
public enum Stat
{
BeginOverlap,
EndOverLap,
InternalEnclosedOverlap,
ExternalEnclosedOverlap,
ContinuousMerge,
NoOverlap
}
public class Interval
{
public int Start;
public int End;
public Interval(int s, int e)
{
Start = s;
End = e;
}
public Stat IsOverlap(Interval inte)
{
if (inte.Start < Start && inte.End > End)
return Stat.ExternalEnclosedOverlap;
else if (inte.Start > Start && inte.End < End && inte.Start < End)
return Stat.InternalEnclosedOverlap;
else if (inte.Start > Start && inte.End > End && inte.Start < End)
return Stat.EndOverLap;
else if (inte.Start < Start && inte.End < End && inte.End > Start)
return Stat.BeginOverlap;
else if (inte.End == Start || inte.Start == End)
return Stat.ContinuousMerge;
else
return Stat.NoOverlap;
}
}
public class IntervalHandler
{
public List<Interval> iList;
public int Length;
public IntervalHandler()
{
iList = new List<Interval>();
Length = 0;
}
public void AddInterval(int s, int e)
{
if (s > e)
return;
if(iList.Count.Equals(0))
{
iList.Add(new Interval(s, e));
return;
}
for(int i = 0; i<iList.Count; i++)
{
switch(iList[i].IsOverlap(new Interval(s, e)))
{
case Stat.BeginOverlap:
iList[i].Start = s;
return;
case Stat.EndOverLap:
HandleEndOverLap(new Interval(s, e));
return;
case Stat.InternalEnclosedOverlap:
return;
case Stat.ExternalEnclosedOverlap:
HandleExternalEnclosedOverLap(new Interval(s, e));
return;
case Stat.ContinuousMerge:
HandleContinuousMerge(i,new Interval(s, e));
return;
}
}
AddNewInterval(new Interval(s, e));
}
private void HandleContinuousMerge(int index, Interval interval)
{
iList[index].Start = Math.Min(iList[index].Start, interval.Start);
iList[index].End = Math.Max(iList[index].End, interval.End);
}
private void AddNewInterval(Interval interval)
{
int i = 0;
while(i < iList.Count && iList[i].Start > interval.Start)
{
i++;
}
iList.Insert(i, interval);
}
private void HandleExternalEnclosedOverLap(Interval interval)
{
//for external enclosed overlap : interval is so fucking big the first interval cant handle shit
//so go over all the intervals till the new intervals end is matched and merge all the passed intervals
int i = 0;
while (iList.Count > 0 && interval.End > iList[i].End && (interval.Start < iList[i].End))
{
if (interval.Start > iList[i].Start)
interval.Start = iList[i].Start;
iList.RemoveAt(i);
}
iList.Insert(0, interval);
}
private void HandleEndOverLap(Interval interval)
{
//for End overlap check for other intervals after the first interval if it overlaps them then merge all of them into one big long interval otherwise merge the first and new interval
int i = 0;
while(iList.Count>0 && interval.End > iList[i].End)
{
iList.RemoveAt(i);
}
if (iList.Count > 0 && iList[i].Start < interval.End)
iList.RemoveAt(i);
iList.Insert(0, interval);
}
public void PrintIntervals()
{
foreach(var interval in iList)
{
Console.WriteLine(interval.Start + " " + interval.End);
}
Console.WriteLine("-------------------------------");
}
}
public static void Main()
{
IntervalHandler handler = new IntervalHandler();
handler.AddInterval(2,4);
handler.AddInterval(1, 2);
handler.AddInterval(4,6);
//handler.AddInterval();
handler.PrintIntervals();
handler.AddInterval(3,5);
handler.PrintIntervals();
Console.Read();
}
}
public class IntervalsTotalTime{
public static class Interval{
int start;
int end;
Interval(int s, int e){
this.start=s;
this.end=e;
}
}
public static int solution(List<Interval> list) {
list.sort((i1, i2) -> (i1.start - i2.start));
int start = list.get(0).start;
int end = list.get(0).end;
int gap = 0;
for(int i=1; i<list.size(); i++) {
Interval interval = list.get(i);
if(interval.start <= end)
end = Math.max(end, interval.end);
else if(interval.start > end) {
gap += interval.start - end;
end = interval.end;
}
}
return end - start - gap;
}
public static void main(String[] args) {
List<Interval> list = new ArrayList();
list.add(new Interval(1,4));
list.add(new Interval(6,8));
list.add(new Interval(2,4));
list.add(new Interval(7,9));
list.add(new Interval(10,15));
System.out.println(solution(list));
}
}
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
public class Facebook1 {
Set<Integer> arraySet = new HashSet<>();
public static void main(String[] args) {
Facebook1 fb1 = new Facebook1();
fb1.totalInterval( new int[][]{ {1, 4}, {6, 8}, {2, 4}, {7, 9}, {10, 15} } );
}
void totalInterval(int[][] input){
int totalInter = 0;
for (int[] inputPair : input) {
int first = inputPair[0];
int second = inputPair[1];
for (int i = first; i < second; i++) {
arraySet.add(i);
}
}
System.out.println(arraySet);
// for (int i = 0; i < arraySet.size(); i ++) {
// if (arraySet.get(i) == 1)
// totalInter = totalInter + 1;
// }
System.out.println(arraySet.size());
}
}
public static int FindInterval(List<Tuple<int, int>> input)
{
if (input == null || !input.Any())
{
return 0;
}
input.Sort();
var interval = 0;
var array = new List<int>();
foreach (var item in input)
{
if (item.Item1 > item.Item2)
{
continue;
}
if (array.Any())
{
if (item.Item1 > array.Min() && item.Item2 < array.Max())
{
continue;
}
if (item.Item1 >= array.Min() && item.Item1 <= array.Max() && item.Item2 > array.Max())
{
interval += item.Item1 - array.Max();
}
else if (item.Item1 < array.Min() && item.Item2 >= array.Min() && item.Item2 <= array.Max())
{
interval += array.Min() - item.Item1;
}
else if (item.Item1 <= array.Min() && item.Item2 >= array.Max())
{
interval = item.Item2 - item.Item1;
}
else
{
interval += item.Item2 - item.Item1;
}
}
else
{
interval += item.Item2 - item.Item1;
}
array.Add(item.Item1);
array.Add(item.Item2);
array.Sort();
}
return interval;
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* Facebook
* <p>
* Given a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals.
* For example:
* input = [(1,4), (2,3)]
* return 3
* input = [(4,6), (1,2)]
* return 3
* input = {{1,4}, {6,8}, {2,4}, {7,9}, {10, 15}}
* return 11
*/
public class Interval {
static class Pair {
int a, b;
Pair(int a, int b) {
this.a = a;
this.b = b;
}
}
List<Pair> list = new ArrayList<>();
void addAll(Pair[] pairs) {
Arrays.stream(pairs).forEach(this::add);
}
void add(Pair p2) {
int min = p2.a, max = p2.b;
for (int i = 0; i < list.size(); i++) {
Pair p1 = list.get(i);
if (!(max < p1.a || min > p1.b)) {
min = Math.min(p1.a, min);
max = Math.max(p1.b, max);
list.remove(i);
}
}
list.add(new Pair(min, max));
}
int getSum() {
return list.stream().mapToInt(p -> p.b - p.a).sum();
}
void clear() {
list.clear();
}
public static void main(String[] args) {
Interval interval = new Interval();
interval.addAll(new Pair[]{new Pair(1, 4), new Pair(2, 3)});
System.out.println(interval.getSum());
interval.clear();
interval.addAll(new Pair[]{new Pair(4, 6), new Pair(1, 2)});
System.out.println(interval.getSum());
interval.clear();
interval.addAll(new Pair[]{new Pair(1, 4), new Pair(6, 8), new Pair(2, 4), new Pair(7, 9), new Pair(10, 15)});
System.out.println(interval.getSum());
interval.clear();
interval.addAll(new Pair[]{new Pair(1, 4), new Pair(6, 8), new Pair(2, 4), new Pair(7, 9), new Pair(10, 15), new Pair(4,6)});
System.out.println(interval.getSum());
interval.clear();
interval.addAll(new Pair[]{new Pair(1, 10), new Pair(5, 8), new Pair(7, 9)});
System.out.println(interval.getSum());
interval.clear();
// { { 3, 7 }, { 4, 5 }, {10, 20}, {8, 15}}
interval.addAll(new Pair[]{new Pair(3, 7), new Pair(4,5), new Pair(10, 20), new Pair(8, 15)});
System.out.println(interval.getSum());
interval.clear();
}
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* Facebook
* <p>
* Given a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals.
* For example:
* input = [(1,4), (2,3)]
* return 3
* input = [(4,6), (1,2)]
* return 3
* input = {{1,4}, {6,8}, {2,4}, {7,9}, {10, 15}}
* return 11
*/
public class Interval {
static class Pair {
int a, b;
Pair(int a, int b) {
this.a = a;
this.b = b;
}
}
List<Pair> list = new ArrayList<>();
void addAll(Pair[] pairs) {
Arrays.stream(pairs).forEach(this::add);
}
void add(Pair p2) {
int min = p2.a, max = p2.b;
for (int i = 0; i < list.size(); i++) {
Pair p1 = list.get(i);
if (!(max < p1.a || min > p1.b)) {
min = Math.min(p1.a, min);
max = Math.max(p1.b, max);
list.remove(i);
}
}
list.add(new Pair(min, max));
}
int getSum() {
return list.stream().mapToInt(p -> p.b - p.a).sum();
}
void clear() {
list.clear();
}
public static void main(String[] args) {
Interval interval = new Interval();
interval.addAll(new Pair[]{new Pair(1, 4), new Pair(2, 3)});
System.out.println(interval.getSum());
interval.clear();
interval.addAll(new Pair[]{new Pair(4, 6), new Pair(1, 2)});
System.out.println(interval.getSum());
interval.clear();
interval.addAll(new Pair[]{new Pair(1, 4), new Pair(6, 8), new Pair(2, 4), new Pair(7, 9), new Pair(10, 15)});
System.out.println(interval.getSum());
interval.clear();
interval.addAll(new Pair[]{new Pair(1, 4), new Pair(6, 8), new Pair(2, 4), new Pair(7, 9), new Pair(10, 15), new Pair(4,6)});
System.out.println(interval.getSum());
interval.clear();
interval.addAll(new Pair[]{new Pair(1, 10), new Pair(5, 8), new Pair(7, 9)});
System.out.println(interval.getSum());
interval.clear();
// { { 3, 7 }, { 4, 5 }, {10, 20}, {8, 15}}
interval.addAll(new Pair[]{new Pair(3, 7), new Pair(4,5), new Pair(10, 20), new Pair(8, 15)});
System.out.println(interval.getSum());
interval.clear();
}
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* Facebook
* <p>
* Given a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals.
* For example:
* input = [(1,4), (2,3)]
* return 3
* input = [(4,6), (1,2)]
* return 3
* input = {{1,4}, {6,8}, {2,4}, {7,9}, {10, 15}}
* return 11
*/
public class Interval {
static class Pair {
int a, b;
Pair(int a, int b) {
this.a = a;
this.b = b;
}
}
List<Pair> list = new ArrayList<>();
void addAll(Pair[] pairs) {
Arrays.stream(pairs).forEach(this::add);
}
void add(Pair p2) {
int min = p2.a, max = p2.b;
for (int i = 0; i < list.size(); i++) {
Pair p1 = list.get(i);
if (!(max < p1.a || min > p1.b)) {
min = Math.min(p1.a, min);
max = Math.max(p1.b, max);
list.remove(i);
}
}
list.add(new Pair(min, max));
}
int getSum() {
return list.stream().mapToInt(p -> p.b - p.a).sum();
}
void clear() {
list.clear();
}
public static void main(String[] args) {
Interval interval = new Interval();
interval.addAll(new Pair[]{new Pair(1, 4), new Pair(2, 3)});
System.out.println(interval.getSum());
interval.clear();
interval.addAll(new Pair[]{new Pair(4, 6), new Pair(1, 2)});
System.out.println(interval.getSum());
interval.clear();
interval.addAll(new Pair[]{new Pair(1, 4), new Pair(6, 8), new Pair(2, 4), new Pair(7, 9), new Pair(10, 15)});
System.out.println(interval.getSum());
interval.clear();
interval.addAll(new Pair[]{new Pair(1, 4), new Pair(6, 8), new Pair(2, 4), new Pair(7, 9), new Pair(10, 15), new Pair(4,6)});
System.out.println(interval.getSum());
interval.clear();
interval.addAll(new Pair[]{new Pair(1, 10), new Pair(5, 8), new Pair(7, 9)});
System.out.println(interval.getSum());
interval.clear();
// { { 3, 7 }, { 4, 5 }, {10, 20}, {8, 15}}
interval.addAll(new Pair[]{new Pair(3, 7), new Pair(4,5), new Pair(10, 20), new Pair(8, 15)});
System.out.println(interval.getSum());
interval.clear();
}
}
#include<iostream>
#include <vector>
#include <map>
int returnHours(vector<vector<int> intervals)
{
int ans=0;
map<int,int> freq;
int sz = intervals.size();
for (int ind=0;ind<sz;++ind)
{
for (int start=intervals[ind][0];start<intervals[ind][1];++start)
{
if(freq[start]==0)
{
freq[start]=1;
++ans;
}
}
return ans;
}
int get_time_covered( int[][] input; int size){
int save = new int[size][2];
int save_size = 0, time_covered = 0;
save[0][0] = input[0][0];
save[0][1] = input[0][1];
save_size = 1;
time_covered = save[0][1] - save[0][0]
for( i = 1; i < size; i++) {
start = input[i][0];
end = input[i][1];
p = -1;
new_start = start;
for( j = 0; j < save_size; j++) {
if( (start > save[j][0] && start < save[j][1]) && save[j][1] > new_start){
new_start = save[j][0]; //8
if( new_start >= end) continue;
p = j;
}
}
time_covered = time_covered + (end - new_start);
if( p > -1){
save[p][1] = new_start;
continue;
}
save[save_size][0] = new_start;
save[save_size][1] = end;
save_size++;
}
return time_covered;
}
Inspired on aonecoding4 I have implemented a Python solution which I find easier to read:
def calcSegments(segments):
segments = sorted(segments, key=lambda segment: segment[0])
last = 0
r = 0
for seg in segments:
l1 = max(last,seg[1])
diff = l1 - max(last, seg[0])
if diff > 0:
r+=diff
last = l1
return r
Instead of sorting, you could use an array of 24 to store the intervals in order, each start index storing the end index.
function getTotalTime(times) {
const intervals = Array(24).fill(0)
for (let t of times) {
let [start, end] = t
if (intervals[start] &&
end > intervals[start]) {
intervals[start] = end
}
else intervals[start] = end
}
// second pass, counting the intervals
let i = 0
let total = 0
let count = 0
let end = 0
while (i < intervals.length) {
if (intervals[i] && intervals[i] > end) {
count += (intervals[i] - i)
// amotize
if (i < end) count -= (end - i)
end = intervals[i]
}
if (i == end) {
total += count
count = 0
}
i += 1
}
return total
}
//Without using arrays.sort and comparator
//using quick sort
static void calcIntervals(){
int[][]segments = {{1,4}, {13,18}, {5,8}, {7,9}, {10, 15}};
int pivot=segments.length/2;
swapElement(segments,pivot, segments.length-1);
sort( segments, 0, segments.length-1);
printArrays(segments);
int lastVal=0;
int totalHrs=0;
for(int i=0; i< segments.length;i++){
totalHrs += Math.max(segments[i][1],lastVal) - Math.max(segments[i][0],lastVal);
lastVal= Math.max(segments[i][1],lastVal);
}
System.out.println("Result="+ totalHrs);
}
static void swapElement(int [][] segments, int a,int b){
int[] temp=segments [a];
segments[a]= segments[b];
segments[b]= temp;
}
static void sort(int [][] segments, int start,int end){
int lastElement= end -1;
if(lastElement> start){
while (start < lastElement){
if(segments[start][0]> segments[end][0]){
swapElement(segments, start, lastElement);
lastElement--;
}else{
start++;
}
}
if(segments[start][0]> segments[end][0]){
swapElement(segments, start, end);
sort(segments,0,start );
sort(segments,start+1,end );
}
}
}
It looks like many of these 'solutions' are wrong. Do they print test cases?
package intervalCover;
import java.util.Arrays;
import java.util.Comparator;
class Interval {
public int a;
public int b;
public Interval(int a, int b) {
this.a = a;
this.b = b;
}
}
class IntervalComp implements Comparator<Interval> {
@Override
public int compare(Interval o1, Interval o2) {
int l = o1.a - o2.a;
int r = o2.b - o2.b;
return l == 0 ? r : l;
}
}
public class IntervalCover {
private static Interval[] p1;
private static Interval[] p2;
private static Interval[] p3;
private static Interval[] p4;
public static void main(String[] args) {
p1 = new Interval[2];
p1[0] = new Interval(1, 4);
p1[1] = new Interval(2, 3);
p2 = new Interval[2];
p2[0] = new Interval(4, 6);
p2[1] = new Interval(1, 2);
p3 = new Interval[5];
p3[0] = new Interval(1, 4);
p3[1] = new Interval(6, 8);
p3[2] = new Interval(2, 4);
p3[3] = new Interval(7, 9);
p3[4] = new Interval(10, 15);
p4 = new Interval[4];
p4[0] = new Interval(1, 4);
p4[1] = new Interval(6, 8);
p4[2] = new Interval(8, 10);
p4[3] = new Interval(10, 15);
System.out.println("one = " + ic(p1) + " correct " + 3);
System.out.println("two = " + ic(p2) + " correct " + 3);
System.out.println("three = " + ic(p3) + " correct " + 11);
System.out.println("four = " + ic(p4) + " correct " + 12);
}
public static int ic(Interval[] intervals) {
Arrays.sort(intervals, new IntervalComp());
int minval = 0;
int sum = 0;
int min = minval;
int max = minval;
int total = 0;
for (Interval i : intervals) {
total = total + (i.b - i.a);
// is there a gap between intervals?
if (i.a >= max) {
if (min == minval) {
min = i.a;
if (i.b > max)
max = i.b;
//System.out.println("FIRST (" + i.a + ", " + i.b + ") " + min + "/" + max + " " + sum);
} else if (max > min) {
sum = sum + (max - min);
//System.out.println("Gap (" + i.a + ", " + i.b + ") " + min + "/" + max + " " + sum);
min = i.a;
max = i.b;
}
} else { // i.a < max
if (min == minval)
min = i.a;
if (i.b > max)
max = i.b;
//System.out.println("Extend (" + i.a + ", " + i.b + ") " + min + "/" + max + " " + sum);
}
}
if (max > min)
sum = sum + (max - min);
// System.out.println("Total = " + total);
return sum;
}
}
def merge(I1,I2):
lp,rp = I1
l,r = I2
# print(lp,rp,l,r)
# complete intersect
if l <= rp and r <= rp:
return [(lp,rp)]
#partial intersect
elif l <= rp and r > rp:
return [(lp,r)]
#no intersection
else:
return []
def intervalTotalRange(arr):
merged = []
for i in range(1,len(arr)):
prev = i -1
curr = i
m = merge(arr[prev],arr[curr])
if len(m) == 1:
merged = arr[0:prev] + m + arr[curr+1:]
return intervalTotalRange(merged)
print(arr)
intervalTotalRange([(1,4),(2,3)])
intervalTotalRange([[1,10],[5,8],[7,9]])
inp = sorted([(1,4), (6,8), (2,4), (7,9),(10,15)])
# print (inp)
intervalTotalRange(inp)
function interval(start,stop){
return {"start": start, "stop": stop};
}
function calculate(intervals){
var arr = [];
intervals.forEach(i => {
for(var tmp = i["start"]; tmp < i["stop"]; tmp++){
arr[tmp] = 1;
}
})
console.log(arr.filter(i => i === 1).length);
}
var intervals = [interval(1,4),
interval(6,8),
interval(2,4),
interval(7,9),
interval(10,15)
]
calculate(intervals);
// Given a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals.
// For example:
// input = [(1, 4), (2, 3)]
// return 3
// input = [(4, 6), (1, 2)]
// return 3
// input = {{ 1, 4 }, { 6, 8 }, { 2, 4 }, { 7, 9 }, { 10, 15 }}
// return 11
function findStartLaterThan(sortedIntervals, value, startPos, endPos) {
var minIndex = startPos || 0
var maxIndex = endPos || sortedIntervals.length
while (maxIndex - minIndex > 0) {
var index = Math.floor((minIndex + maxIndex) / 2)
// console.debug('findStartLaterThan index=' + index)
if (sortedIntervals[index].start <= value && (!sortedIntervals[index + 1] || sortedIntervals[index + 1].start > value)) {
return index
} else if (sortedIntervals[index].start > value) {
maxIndex = index
} else {
minIndex = index
}
}
}
function insertInterval(sortedIntervals, interval) {
var index = findStartLaterThan(sortedIntervals, interval.start)
var endIndex = findStartLaterThan(sortedIntervals, interval.end, index)
if (sortedIntervals.length == 0) {
sortedIntervals.push(interval)
return
}
if (sortedIntervals[index].end >= interval.start) {
if (sortedIntervals[endIndex].end >= interval.end) {
if (index == endIndex) {
// the new interval is dropped
} else {
// index ... endIndex is merged into one, drop the new interval
sortedIntervals[index].end = sortedIntervals[endIndex].end
sortedIntervals.splice(index + 1, endIndex - index)
}
} else {
if (index == endIndex) {
sortedIntervals[index].end = interval.end
}
else {
sortedIntervals[index].end = interval.end
sortedIntervals.splice(index + 1, endIndex - index)
}
}
} else {
if (sortedIntervals[endIndex].end >= interval.end) {
if (index == endIndex) {
// Not possible
} else {
// index ... endIndex is merged into one, drop the new interval
sortedIntervals[endIndex].start = interval.start
sortedIntervals.splice(index + 1, endIndex - index - 1)
}
} else {
if (index == endIndex) {
sortedIntervals.splice(index + 1, 0, interval)
}
else {
sortedIntervals[endIndex].start = interval.start
sortedIntervals[endIndex].end = interval.end
sortedIntervals.splice(index + 1, endIndex - index - 1)
}
}
}
}
function count(randomIntervals) {
var sortedIntervals = [{ start: 0, end: 0 }]
for (var interval of randomIntervals) {
insertInterval(sortedIntervals, { start: interval[0], end: interval[1], })
}
var sum = 0
for (var interval of sortedIntervals) {
sum += interval.end - interval.start
}
return sum
}
console.log(count([[1, 4], [2, 3]]))
console.log(count([[4, 6], [1, 2]]))
console.log(count([[1, 4], [6, 8], [2, 4], [7, 9], [10, 15]]))
public class Node {
int low; int high; Node left; Node right;
Node(int low, int high) {
this.low = low;
this.high = high;
this.left=null;
this.right=null;
}
static Node insert(int low, int high, Node root) {
if (root == null)
return new Node(low, high);
// lies within root interval, do nothing
if (root.low <= low && root.high>=high)
return root;
// lies to right, no intersection
if (root.high <= low) {
root.left = insert(low, high, root.left);
return root;
}
// lies to left, no intersection
if (root.low >= high) {
root.right = insert(low, high, root.right);
return root;
}
// intersect with left boundary
if (root.low > low) {
root.left = insert(low, root.low, root.left);
}
// intersect with right boundary
if (root.high < high) {
root.right = insert(root.high, high, root.right);
}
return root;
}
static int count(Node root) {
if (root == null) return 0;
return root.high - root.low + count(root.left) + count(root.right);
}
public static void main(String args[]){
Node root = null;
root = insert(1,4, root);
root = insert(2,10, root);
root = insert(1,7, root);
System.out.println(count(root));
}
}
public class Node {
int low; int high; Node left; Node right;
Node(int low, int high) {
this.low = low;
this.high = high;
this.left=null;
this.right=null;
}
static Node insert(int low, int high, Node root) {
if (root == null)
return new Node(low, high);
// lies within root interval, do nothing
if (root.low <= low && root.high>=high)
return root;
// lies to right, no intersection
if (root.high <= low) {
root.left = insert(low, high, root.left);
return root;
}
// lies to left, no intersection
if (root.low >= high) {
root.right = insert(low, high, root.right);
return root;
}
// intersect with left boundary
if (root.low > low) {
root.left = insert(low, root.low, root.left);
}
// intersect with right boundary
if (root.high < high) {
root.right = insert(root.high, high, root.right);
}
return root;
}
static int count(Node root) {
if (root == null) return 0;
return root.high - root.low + count(root.left) + count(root.right);
}
public static void main(String args[]){
Node root = null;
root = insert(1,4, root);
root = insert(2,10, root);
root = insert(1,7, root);
System.out.println(count(root));
}
}
using System;
using System.Collections.Generic;
using System.Text;
namespace Facebook
{
public class TimeInterval
{
public void CoveredTime()
{
List<int[]> list = new List<int[]>()
{
new int[] {1,6},
new int[] {2,9},
new int[] {3,5}
};
Console.WriteLine(CoveredTime(list));
Console.ReadLine();
}
public int CoveredTime(List<int[]> list)
{
if (list == null || list.Count == 0) return 0;
int coveredTime = list[0][1] - list[0][0];
List<int[]> coveredList = new List<int[]>();
coveredList.Add(list[0]);
for(int i=1; i<list.Count;i++)
{
coveredTime += GetCoveredTime(coveredList, list[i]);
}
return coveredTime;
}
private int GetCoveredTime(List<int[]> list, int[] interval)
{
int covered = 0;
foreach(int[] period in list)
{
if(interval[0] < period[0] && interval[1] <=period[0])
{
if (interval[1] == period[0])
{
period[0] = interval[0];
}
covered = interval[1] - interval[0];
break;
}
else if(interval[0] >= period[1])
{
if(interval[0] == period[1])
{
period[1] = interval[1];
}
covered = interval[1] - interval[0];
break;
}
else if(interval[0] >= period[0] && interval[0] < period[1] && interval[1] > period[1])
{
covered = interval[1] - period[1];
period[1] = interval[1];
break;
}
}
return covered;
}
}
}
public class FindTotalTimeIntervals {
public static void main(String[] args) {
List<Integer[]> input = new ArrayList<>();
input.add(new Integer[]{1,4});
input.add(new Integer[]{6,8});
input.add(new Integer[]{2,4});
input.add(new Integer[]{7,9});
input.add(new Integer[]{10,15});
Set<String> set = new HashSet<>();
input.forEach(array -> {
int start = array[0];
int end = array[1];
for(int i = start; i < end; i++) {
String key = i + "-" + (i + 1);
set.add(key);
}
});
System.out.println(set.size());
}
}
#include <iostream>
#include <set>
#include <vector>
int main ()
{
std::set<int> myset;
std::set<int>::iterator it_up, it_low;
std::vector<std::pair<int,int>> freq;
std::pair<int, int> p1 = { 1, 4 };
std::pair<int, int> p2 = { 6, 8 };
std::pair<int, int> p3 = { 2, 4 };
std::pair<int, int> p4 = { 7, 9 };
std::pair<int, int> p5 = { 10, 15 };
freq.push_back(p1);
freq.push_back(p2);
freq.push_back(p3);
freq.push_back(p4);
freq.push_back(p5);
for (auto it = freq.begin(); it != freq.end(); it++) {
it_up = myset.upper_bound(it->first);
it_low = myset.lower_bound(it->first);
if (it_up == myset.end() || it_low == myset.begin()) {
myset.insert(it->first);
}
it_up = myset.upper_bound(it->second);
if (it_up == myset.end()) {
myset.insert(it->second);
it_low = myset.lower_bound(it->second);
auto nx = std::prev(it_low, 1);
if (*nx != it->first) {
myset.erase(nx);
}
}
}
int sum = 0;
auto it = myset.begin();
for (int i = 0; i < myset.size() - 1; i+=2) {
auto nx = std::next(it, 1);
sum += abs(*nx - *(it));
it = std::next(it, 2);
}
std::cout << sum << '\n';
return 0;
}
#include <iostream>
#include <set>
#include <vector>
int main ()
{
std::set<int> myset;
std::set<int>::iterator it_up, it_low;
std::vector<std::pair<int,int>> freq;
std::pair<int, int> p1 = { 1, 4 };
std::pair<int, int> p2 = { 6, 8 };
std::pair<int, int> p3 = { 2, 4 };
std::pair<int, int> p4 = { 7, 9 };
std::pair<int, int> p5 = { 10, 15 };
freq.push_back(p1);
freq.push_back(p2);
freq.push_back(p3);
freq.push_back(p4);
freq.push_back(p5);
for (auto it = freq.begin(); it != freq.end(); it++) {
it_up = myset.upper_bound(it->first);
it_low = myset.lower_bound(it->first);
if (it_up == myset.end() || it_low == myset.begin()) {
myset.insert(it->first);
}
it_up = myset.upper_bound(it->second);
if (it_up == myset.end()) {
myset.insert(it->second);
it_low = myset.lower_bound(it->second);
auto nx = std::prev(it_low, 1);
if (*nx != it->first) {
myset.erase(nx);
}
}
}
int sum = 0;
auto it = myset.begin();
for (int i = 0; i < myset.size() - 1; i+=2) {
auto nx = std::next(it, 1);
sum += abs(*nx - *(it));
it = std::next(it, 2);
}
std::cout << sum << '\n';
return 0;
}
With some bit operation
public class TimeSlot {
public static int findUsedTimeSlots(int[][] times) {
if(times == null || times[0].length!= 2)
return -1;
int usedTime =0;
for(int i = 0; i < times.length; i++) {
for(int j = times[i][0]; j < times[i][1]; j++) {
usedTime |= 1 << j;
}
}
int count = 0;
while(usedTime != 0) {
usedTime = usedTime & (usedTime -1);
count++;
}
return count;
}
public static void main(String[] args) {
int[][] times = new int[][]{{1,4}, {6,8}, {2,4}, {7,9}, {10,15}};
System.out.println(findUsedTimeSlots(times));
}
}
int time_covered(const std::vector<std::pair<int, int>>& intervals) {
if (intervals.empty()) {
return 0;
}
auto sorted_intervals = intervals;
std::sort(sorted_intervals.begin(), sorted_intervals.end(), [](const std::pair<int, int>& pa, const std::pair<int, int>& pb) { return pa.first < pb.first; });
int sum = 0;
int start = sorted_intervals[0].first;
int end = sorted_intervals[0].second;
for (int i = 1; i < sorted_intervals.size(); ++i) {
if (sorted_intervals[i].first <= end) {
end = std::max(sorted_intervals[i].second, end);
}
else {
sum += end - start;
start = sorted_intervals[i].first;
end = sorted_intervals[i].second;
}
}
sum += end - start;
return sum;
}
def flattern_sum(intervals):
result = [0] * 24
for i in intervals:
start_time, end_time = i
for time_interval in range(start_time, end_time, 1):
result[time_interval-1] = 1
return sum(result)
And some tests
def tests():
input0 = [(1,10),(5,8),(7,9)]
temp_result = flattern_sum(input0)
if temp_result != 9:
print(f"test failed {temp_result}")
else:
print("Test1: Ok")
input1 = [(1,4), (2,3)]
temp_result = flattern_sum(input1)
if temp_result != 3:
print(f"test failed {temp_result}")
else:
print("Test1: Ok")
input2 = [(4,6), (1,2)]
temp_result = flattern_sum(input2)
if temp_result != 3:
print(f"test failed {temp_result}")
else:
print("Test1: Ok")
input3 = [(1,4), (6,8), (2,4), (7,9), (10, 15)]
temp_result = flattern_sum(input3)
if temp_result != 11:
print(f"test failed {temp_result}")
else:
print("Test1: Ok")
if __name__ == "__main__":
tests()
static int solve(int[][] intervals){
Arrays.sort(intervals, (a,b)->a[0]-b[0]);
PriorityQueue<Integer> queue = new PriorityQueue<>();
Deque<Integer> deque = new ArrayDeque<>();
queue.add(intervals[0][1]);
deque.add(intervals[0][0]);
int count = 0;
int start = 0;
int end = 0;
for(int i=1;i<intervals.length;i++){
if(intervals[i][0]>queue.peek()){
end = 0;
while(!queue.isEmpty() && queue.peek()<intervals[i][0]){
end = queue.remove();
}
start = deque.getFirst();
deque.clear();
count += end-start;
}
queue.add(intervals[i][1]);
deque.add(intervals[i][0]);
}
start = deque.getFirst();
while(!queue.isEmpty()){
end = queue.remove();
}
count += end-start;
return count;
}
static int[][] solve(int[][] intervals){
Arrays.sort(intervals, (a,b)->a[0]-b[0]);
int start = intervals[0][0];
int end = intervals[0][1];
List<int[]> list = new ArrayList<>();
for(int i=1;i<intervals.length;i++){
int currStart = intervals[i][0];
int currEnd = intervals[i][1];
if(currStart<=end && currEnd>=end){
end = currEnd;
}else if(currStart>end){
list.add(new int[]{start,end});
start = currStart;
end = currEnd;
}
}
list.add(new int[]{start,end});
int[][] res = new int[list.size()][2];
for(int i=0;i<res.length;i++){
res[i] = list.get(i);
}
return res;
}
Looking for interview questions sharing and mentors?
- aonecoding4 January 19, 2019Visit A++ Coding Bootcamp at aonecode.com
We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding, algorithms, system design to mock interviews.
All classes are given by experienced engineers/interviewers from FB, Google and Uber.
Our students got offers from Google, Uber, Facebook, Amazon and other top companies after a few weeks of training.