Facebook Interview Question Software Developers
Country: United States
Interview Type: Phone Interview
private List<int[]> mergeIntervals(List<List<int[]>> list) {
List<int[]> result = new ArrayList<>();
List<int[]> intervals = new ArrayList<>();
for(List<int[]> item : list) {
for(int[] i : item) {
intervals.add(i);
}
}
Collections.sort(intervals, new Comparator<int[]>(){
public int compare(int[] a, int[] b) {
return a[0] - b[0];
}
});
int[] period = new int[]{intervals.get(0)[0], intervals.get(0)[1]};
for(int i=1; i<intervals.size(); ++i) {
if(period[1] >= intervals.get(i)[0]) {
if (intervals.get(i)[1] > period[1])
period[1] = intervals.get(i)[1];
} else {
result.add(period);
period = new int[]{intervals.get(i)[0], intervals.get(i)[1]};
}
}
result.add(period);
return result;
}
This is quite clever and is elegant in its simplicity and robustness: it can handle not just two lists as inputs, but arbitrarily many.
The caveat may be for larger lists. Since it makes an additional copy of the inputs and then performs a preliminary sort, there's additional memory overhead and the performance is constrained by the sorting step which is generally limited to O(n log(n)). For smaller datasets this is not a problem.
Making use of the fact that the inputs are sorted, we can achieve O(n) performance since we can traverse the inputs in-order and do a single pass and also perform a O(n) comparisons (with a slightly larger coefficient). Again, this would only matter for larger inputs.
Also, while this can be done with arbitrarily many input lists, so long as all are sorted, there's more effort involved in doing the comparisons and internal "bookkeeping" so, to keep it simple, I opted for the two-list input as stated. Finally, the problem doesn't explicitly state it, but I assume that each individual input list does not contain any overlapping intervals - that is, each list's intervals are already disjoint and we're merging to create a single list with any cross-list overlapping ranges merged, but no need to merge ranges within a single list. (We could add a pre-processing step to handle the case of overlapping intervals in the inputs.)
In Java this is:
package com.ezraepstein.careercup.fb;
import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;
import java.util.StringJoiner;
public class MergeIntervals {
private static boolean isInRangeInclusive(int[] r, int x) {
return r[0] <= x && x<= r[1];
}
/**
* Extends the range (r) based on the ranges in the takeFrom list.
* @param r the current range
* @param takeFrom sorted list of ranges to examine
* @param idx current index into the list of ranges being examined
* @return the new index value.
*/
private static int coalesceIntervals(int[] r, List<int[]> takeFrom, int idx) {
while (idx < takeFrom.size() && isInRangeInclusive(r, takeFrom.get(idx)[0])) {
r[1] = Math.max(r[1], takeFrom.get(idx)[1]);
++idx;
}
return idx;
}
/**
* Merge two lists of ordered (sorted) disjoint ranges to create a single such list.
* <p>
* The input lists must be sorted ascending with only disjoint ranges. This function does not
* check and so no guarantees are made if invalid data are provided.
* </p>
*
* @param lh the first input list (aka, the "left-hand" list to be merged)
* @param rh the secong input list (aka, the "right-hand" one)
* @return the combined list of contiguous ranges.
*/
public static List<int[]> mergeIntervals(final List<int[]> lh, List<int[]> rh) {
List<int[]> result = new ArrayList<int[]>(Math.max(32, lh.size()));
int i = 0, j = 0; // indices into lh and rh, respectively
int[] r; // the current range, will be assigned in the loop
// move along both lists, taking from whichever has the smaller starting range at the current indices.
while (i<lh.size() && j<rh.size()) {
if (lh.get(i)[0] <= rh.get(j)[0]) {
r = lh.get(i++);
j = coalesceIntervals(r, rh, j);
} else {
r = rh.get(j++);
i = coalesceIntervals(r, lh, j);
}
result.add(r);
}
// may have only finished taking items from one list, so check that and copy as needed
if (i < lh.size()) {
result.addAll(lh.subList(i, lh.size()));
} else if (j < rh.size()) {
result.addAll(rh.subList(j, rh.size()));
}
return result;
}
static String intListArrayAsString(List<int[]> l) {
final StringJoiner sj = new StringJoiner(", ");
l.forEach(x -> sj.add(Arrays.toString(x)));
return sj.toString();
}
}
tested via:
package com.ezraepstein.careercup.fb;
import org.junit.Test;
import java.util.Arrays;
import java.util.List;
public class MergeIntervalsTest {
@Test
public void coalesceIntervals() {
List<int[]> lh = Arrays.asList(new int[]{1,2}, new int[]{3,9});
List<int[]> rh = Arrays.asList(new int[]{4,5}, new int[]{8,10}, new int[]{11, 12});
System.out.println("List 1: " + MergeIntervals.intListArrayAsString(lh));
System.out.println("List 2: " + MergeIntervals.intListArrayAsString(rh));
final List<int[]> result = MergeIntervals.mergeIntervals(lh, rh);
System.out.println("O/P: " + MergeIntervals.intListArrayAsString(result));
}
}
with output:
List 1: [1, 2], [3, 9]
List 2: [4, 5], [8, 10], [11, 12]
O/P: [1, 2], [3, 10], [11, 12]
Process finished with exit code 0
solution in C
1. build sorted array of all starting points and another array for all ending points then
2. use following algorithm to build result array
// create sorted array first
while(i<array_size && j<array_size)
{
result[cnt][0] = start_point[i++];
while(end_point[j] > start_point[i])
{
i++; j++;
}
result[cnt][1] = end_point[j++];
cnt++;
}
public int[][] mergeInterval(int[][] list1, int[][] list2) {
int maxLen = (list1.length >= list2.length ? list1.length : list2.length);
int[][] result = new int[maxLen][2];
for(int i = 0; i < maxLen; i++) {
if(list1.length <= i){
result[i] = list2[i];
} else if(list2.length <= i) {
result[i] = list1[i];
} else {
int startA = list1[i][0];
int startB = list2[i][0];
int endA = list1[i][1];
int endB = list2[i][1];
result[i][0] = (startA < startB ? startA : startB);
result[i][1] = (endA > endB ? endA : endB);
}
}
return result;
}
public int[][] mergeInterval(int[][] list1, int[][] list2) {
int maxLen = (list1.length >= list2.length ? list1.length : list2.length);
int[][] result = new int[maxLen][2];
for(int i = 0; i < maxLen; i++) {
if(list1.length <= i){
result[i] = list2[i];
} else if(list2.length <= i) {
result[i] = list1[i];
} else {
int startA = list1[i][0];
int startB = list2[i][0];
int endA = list1[i][1];
int endB = list2[i][1];
result[i][0] = (startA < startB ? startA : startB);
result[i][1] = (endA > endB ? endA : endB);
}
}
return result;
}
public int[][] mergeInterval(int[][] list1, int[][] list2) {
int maxLen = (list1.length >= list2.length ? list1.length : list2.length);
int[][] result = new int[maxLen][2];
for(int i = 0; i < maxLen; i++) {
if(list1.length <= i){
result[i] = list2[i];
} else if(list2.length <= i) {
result[i] = list1[i];
} else {
int startA = list1[i][0];
int startB = list2[i][0];
int endA = list1[i][1];
int endB = list2[i][1];
result[i][0] = (startA < startB ? startA : startB);
result[i][1] = (endA > endB ? endA : endB);
}
}
return result;
}
Test code is below
@Test
public void test_mergeArrayInterval() {
int[][] list1 = new int[][] {{1,2}, {3,9}};
int[][] list2 = new int[][] {{4,5}, {8, 10}, {11, 12}};
int[][] result = new ArrayIntervalMerge().mergeInterval(list1, list2);
for(int i = 0; i < result.length; i++) {
System.out.println(Arrays.toString(result[i]));
}
}
And result is
1, 5]
[3, 10]
[11, 12]
It's trickier than it seems:
Swift
class Sequence {
let a: [[Int]]
let b: [[Int]]
var ia = 0
var ib = 0
init(a: [[Int]], b: [[Int]]) {
self.a = a
self.b = b
}
func getNext() -> [Int]? {
let r1 = ia < a.count ? a[ia] : nil
let r2 = ib < b.count ? b[ib] : nil
if let r1 = r1, let r2 = r2 {
if r1[0] <= r2[0] {
ia += 1
return r1
} else {
ib += 1
return r2
}
} else {
if let r1 = r1 {
ia += 1
return r1
}
if let r2 = r2 {
ib += 1
return r2
}
}
return nil
}
}
func isIntersect(a:[Int], b:[Int]) -> Bool {
if a[0] < b[0] {
return a[1] >= b[0]
} else {
return b[1] >= a[0]
}
}
func mergeSequences(a: [[Int]], b: [[Int]]) -> [[Int]] {
var result: [[Int]] = []
let s = Sequence(a: a, b: b)
var woking = s.getNext()
if woking != nil {
while woking != nil {
let next = s.getNext()
if let next = next {
if isIntersect(a: woking!, b: next) {
woking = [min(woking![0],next[0]), max(woking![1], next[1])]
} else {
result.append(woking!)
woking = next
}
} else {
result.append(woking!)
woking = nil
}
}
}
return result
}
print(mergeSequences(a: [[1, 2], [3,9]], b: [[4,5], [8,10], [11, 12]])) // [[1, 2], [3, 10], [11, 12]]
print(mergeSequences(a: [[1, 2], [7,9]], b: [[4,5], [8,10], [11, 12]])) // [[1, 2], [4, 5], [7, 10], [11, 12]]
print(mergeSequences(a: [[1, 4], [7,9], [8,11]], b: [[4,5], [11, 12]])) // [[1, 5], [7, 12]]
Java 8 solution:
List<List<Integer>> exo(List<List<Integer>> a, List<List<Integer>> b) {
a.addAll(b);
Collections.sort(a, (l1, l2) -> l1.get(0).compareTo(l2.get(0)));
for (int i = 0; i < a.size(); i++) {
for (int j = i + 1; j < a.size(); j++) {
if (a.get(i).get(1) < a.get(j).get(0)) {
continue;
}
if (a.get(i).get(1) > a.get(j).get(1)) {
a.remove(j);
} else {
a.get(i).set(1, a.get(j).get(1));
a.remove(j);
}
j--;
}
}
return a;
}
private static int[][] merge2(int[][] a1, int[][] a2){
Integer[][] combined = combine(a1, a2);
List<Integer[]> ret = new ArrayList<>();
ret.add(combined[0]);
Integer[] lastInsert = ret.get(0);
for(int i=1; i< combined.length; i++) {
if(combined[i][0] <= lastInsert[1]
&& combined[i][1] > lastInsert[1]) {
lastInsert[1] = combined[i][1];
}else if(combined[i][1] < lastInsert[1]) {
continue;
}else {
ret.add(combined[i]);
}
lastInsert = ret.get(ret.size()-1);
}
int[][] y = new int[ret.size()][];
for(int n=0; n<ret.size(); n++) {
int[] m = {ret.get(n)[0], ret.get(n)[1]};
y[n] = m;
}
return y;
}
private static Integer[][] combine(int[][] a1, int[][] a2){
Integer[][] combined = new Integer[a1.length + a2.length][];
int c_idx = 0;
int i1 = 0, i2 = 0;
while(i1 < a1.length && i2 < a2.length) {
if(a1[i1][0] <= a2[i2][0]) {
Integer[] x = {a1[i1][0], a1[i1][1]};
combined[c_idx] = x;
i1++;
}else {
Integer[] x = {a2[i2][0], a2[i2][1]};
combined[c_idx] = x;
i2++;
}
c_idx++;
}
if(i1 < a1.length) {
for(int k=i1; k<a1.length; k++) {
Integer[] x = {a1[k][0], a1[k][1]};
combined[c_idx] = x;
c_idx++;
}
}
if(i2 < a2.length) {
for(int k=i2; k<a2.length; k++) {
Integer[] x = {a2[k][0], a2[k][1]};
combined[c_idx] = x;
c_idx++;
}
}
return combined;
}
public ArrayList mergeIntervals(List list1, List list2){
int len1 = 0;
int len2 = 0;
int max = 0;
ArrayList<int[]> finalArray = new ArrayList<int[]>();
while(max < list1.size()+list2.size()){
if(len1 == list1.size() || len2 == list2.size()){
for(int i = len1; i < list1.size() ; i ++){
finalArray.add((int[])list1.get(len1));
len1++;
}
for(int i = len2; i < list2.size() ; i ++){
finalArray.add((int[])list2.get(len2));
len2++;
}
} else{
int[] array1 = (int[])list1.get(len1);
int[] array2 = (int[])list2.get(len2);
int[] result = new int[2];
if(array1[0] <= array2[0]){
result[0] = array1[0];
if(array2[0] >= array1[0] && array2[0] <= array1[1] ){
if(array1[1] >= array2[1] ){
result[1] = array1[1];
}else{
result[1] = array2[1];
}
len2++;
}else{
result[1] = array1[1];
}
len1++;
finalArray.add(result);
}else {
result[0] = array2[0];
if(array1[0] >= array2[0] && array1[0] <= array2[1] ){
if(array1[1] >= array2[1] ){
result[1] = array1[1];
}else{
result[1] = array2[1];
}
len1++;
}else{
result[1] = array2[1];
}
len2++;
finalArray.add(result);
}
}
max = len1+len2;
}
return finalArray;
}
and
boolean canMerge(int[] arr1, int[] arr2){
return arr1[1] >= arr2[0];
}
int[] mergeLocal(int[] arr1, int[] arr2){
int[] merged = new int[2];
// Determine first element [1,2] [2,3] .... [2,8] [3,6]
if(arr1[0] < arr2[0]){
merged[0] = arr1[0];
}
// Determins second element [1,2] [2,3] .... [2,8] [3,6]
if(arr1[1] > arr2[1]){
merged[1] = arr1[1];
}else{
merged[1] = arr2[1];
}
return merged;
}
List<int[]> mergeArrays(List<int[]> arr1, List<int[]> arr2){
List<int[]> mergedArray = new ArrayList<>();
// Merge array 1
int i = 1;
mergedArray.add(arr1.get(0));
int j = 0;
while(i < arr1.size()){
if(canMerge(mergedArray.get(j),arr1.get(i))){
mergedArray.set(j,mergeLocal(mergedArray.get(j),arr1.get(i)));
}else{
mergedArray.add(arr1.get(i));
j++;
}
i++;
}
// Merge Array 2
int k = 0 ;
while(k < arr2.size()){
if(canMerge(mergedArray.get(j),arr2.get(k))){
mergedArray.set(j,mergeLocal(mergedArray.get(j),arr2.get(k)));
}else{
mergedArray.add(arr2.get(k));
j++;
}
k++;
}
return mergedArray;
}
and
public static int[][] mergeInterval(int[][] list1, int[][] list2) {
LinkedList<int[]> result = new LinkedList<>();
result.add(list1[0]);
int i =1;
int j =0;
while(i < list1.length && j < list2.length) {
int[] secondInterval;
int[] a = i < list1.length ? list1[i] : null;
int[] b = j < list2.length ? list2[j] : null;
if(a[0] < b[0]) {
secondInterval = a;
i++;
} else {
secondInterval = b;
j++;
}
mergeWithResult(result, secondInterval);
}
while(i < list1.length) {
mergeWithResult(result, list1[i++]);
}
while(j < list2.length) {
mergeWithResult(result, list2[j++]);
}
int[][] resultArray = new int[result.size()][2];
int k =0;
for(int[] element: result) {
resultArray[k++] = element;
}
return resultArray;
}
private static void mergeWithResult(LinkedList<int[]> result, int[] secondInterval) {
int[] lastInterval = result.getLast();
if(lastInterval[1] < secondInterval[0]) {
result.add(secondInterval);
} else {
result.getLast()[1] = Math.max(result.getLast()[1], secondInterval[1]);
}
}
public ArrayList<int[]> mergeIntervalsLists(ArrayList<int[]> a1, ArrayList<int[]> a2) {
List<int[]> merge = new ArrayList();
int i1 = 0;
int i2 = 0;
while (i1 < a1.size() && i2 < a2.size()) {
int interval[] = new int[2];
interval[0] = a1.get(i1)[0] <= a2.get(i2)[0] ? a1.get(i1)[0] : a2.get(i2)[0];
if (a1.get(i1)[1] == a2.get(i2)[1]) {
interval[1] = a1.get(i1)[1];
} else if (a1.get(i1)[1] < a2.get(i2)[1]) {
while (i1 < a1.size() && a1.get(i1)[1] < a2.get(i2)[1]) {
i1++;
};
interval[1] = i1 < a1.size() ? a1.get(i1)[1] : a2.get(i2)[1];
} else {
while (i2 < a2.size() && a2.get(i2)[1] < a1.get(i1)[1]) {
i2++;
};
interval[1] = i2 < a2.size() ? a2.get(i2)[1] : a1.get(i1)[1];
}
i1++;
i2++;
merge.add(interval);
}
while(i1 < a1.size()) {
int interval[] = new int[2];
interval[0] = a1.get(i1)[0];
interval[1] = a1.get(i1++)[1];
merge.add(interval);
}
while(i2 < a2.size()) {
int interval[] = new int[2];
interval[0] = a2.get(i2)[0];
interval[1] = a2.get(i2++)[1];
merge.add(interval);
}
return merge;
}
Tested by:
ArrayList<int[]> a1 = new ArrayList();
ArrayList<int[]> a2 = new ArrayList();
/*a1.add(new int[] {1,2});
a1.add(new int[] {3,9});
a1.add(new int[] {15,19});
a2.add(new int[] {1,2});
a2.add(new int[] {3,7});
a2.add(new int[] {8,12}); */
a1.add(new int[] {1,2});
a1.add(new int[] {3,9});
a1.add(new int[] {15,19});
a2.add(new int[] {1,2});
a2.add(new int[] {3,7});
a2.add(new int[] {8,12});
javascript
const _mergeOrConcatIntervals = (firstInterval, secondInterval) => {
const result = [];
if (!firstInterval || !secondInterval){
result.push(firstInterval || secondInterval);
}else if ((firstInterval[1] >= secondInterval[0] && firstInterval[1] <= secondInterval[1]) ||
(secondInterval[1] >= firstInterval[0] && secondInterval[1] <= firstInterval[1])){
result.push([
Math.min(firstInterval[0], secondInterval[0]),
Math.max(firstInterval[1], secondInterval[1])
]);
} else{
result.push(...[firstInterval, secondInterval].sort((a,b) => a[1] - b[1]));
}
return result;
}
const mergeIntervals = (firstArray, secondArray) => {
const mergedArray = [];
let i=0, j=0;
while (i<firstArray.length || j<secondArray.length){
let currentInterval;
const lastMergedInterval = mergedArray.pop();
if (i >= firstArray.length || secondArray[j][0] <= firstArray[i][0]){
currentInterval = secondArray[j];
j++;
} else{
currentInterval = firstArray[i];
i++;
}
let result = _mergeOrConcatIntervals(lastMergedInterval, currentInterval);
mergedArray.push(...result);
}
return mergedArray;
};
merge(x,y) {
Var res = [];
Var I = 0;
Var j = 0;
While (I < x.length && j < y.length) {
If (x[I,1] < y[j,0]) {
Res.push(x[I]);
I++;
Continue;
}
If (y[I,1] < x[j,0]) {
Res.push(y[I]);
j++;
Continue;
}
y[j,0] = Math.min(x[I,0], y[j,0]);
y[j,1] = Math.max(x[I,1], y[j,1]);
I++;
}
Return res;
}
merge(x,y) {
var res = [];
var i = 0;
var j = 0;
while (i < x.length && j < y.length) {
if (x[i,1] < y[j,0]) {
res.push(x[i]);
i++;
continue;
}
if (y[i,1] < x[j,0]) {
res.push(y[i]);
j++;
Continue;
}
y[j,0] = Math.min(x[i,0], y[j,0]);
y[j,1] = Math.max(x[i,1], y[j,1]);
i++;
}
return res;
}
def merge(l1, l2):
intervals = []
inputs = sorted(l1 + l2)
cur_s, cur_e = None, None
for s, e in inputs:
if cur_s is None:
cur_s = s
cur_e = e
elif s <= cur_e:
cur_e = max(cur_e, e)
else:
intervals.append((cur_s, cur_e))
cur_s = s
cur_e = e
if cur_s:
intervals.append((cur_s, cur_e))
return intervals
public static void MergeIntervals(List<Tuple<int, int>> input)
{
if(input == null || !input.Any())
{
return;
}
input.Sort();
var array = new List<int>();
foreach (var interval in input)
{
if (array.Any())
{
if (interval.Item1 >= array.Min() && interval.Item2 <= array.Max())
{
continue;
}
if (interval.Item1 >= array.Min() && interval.Item1 <= array.Max() && interval.Item2 > array.Max())
{
array.Remove(array.Max());
array.Add(interval.Item2);
}
else if (interval.Item1 < array.Min() && interval.Item2 >= array.Min() && interval.Item2 <= array.Max())
{
array.Remove(array.Min());
array.Add(interval.Item1);
}
else
{
array.Add(interval.Item1);
array.Add(interval.Item2);
}
}
else
{
array.Add(interval.Item1);
array.Add(interval.Item2);
}
}
Why Everyone writing so complex code; here is very simple
package Java;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
/**
* Author: Nitin Gupta(nitin.gupta@walmart.com)
* Date: 31/03/19
* Description:
*/
public class MergeSortedListOfInterval {
static class Interval {
public int start, end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Interval interval = (Interval) o;
return start == interval.start &&
end == interval.end;
}
@Override
public int hashCode() {
return Objects.hash(start, end);
}
@Override
public String toString() {
return "(" + start + "," + end + ')';
}
}
private static void test(List<Interval> a, List<Interval> b) {
System.out.println();
merge(a, b).stream().forEach(x -> System.out.print(x + "->"));
}
public static void main(String args[]) {
List<Interval> a = new ArrayList<>();
List<Interval> b = new ArrayList<>();
a.add(new Interval(1, 2));
a.add(new Interval(3, 9));
a.add(new Interval(12, 15));
b.add(new Interval(4, 6));
b.add(new Interval(8, 10));
b.add(new Interval(11, 12));
test(a, b);
a.clear();
b.clear();
a.add(new Interval(1, 5));
a.add(new Interval(10, 14));
a.add(new Interval(16, 18));
b.add(new Interval(2, 6));
b.add(new Interval(8, 10));
b.add(new Interval(11, 20));
test(a, b);
a.clear();
b.clear();
/**
* [(1,2),(3,4)]
* [(2,3),(5,6)]
*
* [(1,3)
*/
a.add(new Interval(1, 2));
a.add(new Interval(3, 4));
b.add(new Interval(2, 3));
b.add(new Interval(5, 6));
test(a, b);
}
private static boolean areOverlap(Interval a, Interval b) {
if (a == null || b == null)
return false;
if (a.end < b.start || b.end < a.start)
return false;
return true;
}
private static Interval merge(Interval a, Interval b) {
if (areOverlap(a, b)) {
return new Interval(Math.min(a.start, b.start), Math.max(a.end, b.end));
}
return null;
}
private static List<Interval> merge(List<Interval> a, List<Interval> b) {
if (a == null || a.isEmpty())
return b;
if (b == null || b.isEmpty())
return a;
final LinkedList<Interval> resuList = new LinkedList<>();
int aIndex = 0, bIndex = 0;
int aSize = a.size(), bSize = b.size();
while (aIndex < aSize && bIndex < bSize) {
Interval x = a.get(aIndex);
Interval y = b.get(bIndex);
Interval z = resuList.isEmpty() ? null : resuList.getLast();
Interval finalInterval = null;
if (x.end < y.start) {
mergeUpdate(x, z, resuList);
aIndex++;
} else if (y.end < x.start) {
mergeUpdate(y, z, resuList);
bIndex++;
} else {
aIndex++;
bIndex++;
mergeUpdate(merge(x, y), z, resuList);
}
}
while (aIndex < aSize){
Interval x= a.get(aIndex++);
Interval z = resuList.isEmpty() ? null : resuList.getLast();
mergeUpdate(x, z, resuList);
}
while (bIndex < bSize){
Interval x= b.get(bIndex++);
Interval z = resuList.isEmpty() ? null : resuList.getLast();
mergeUpdate(x, z, resuList);
}
return resuList;
}
private static void mergeUpdate(Interval finalInterval, Interval z, List<Interval> result) {
Interval merged = merge(finalInterval, z);
if (merged != null) {
z.start = merged.start;
z.end = merged.end;
} else {
result.add(finalInterval);
}
}
}
def merge_intervals(l1, l2):
intervals = sorted(l1 + l2, key=lambda x: x[0])
if len(intervals) < 2:
return intervals
prev_left = intervals[0][0]
prev_right = intervals[0][1]
result = []
for i in range(1, len(intervals)):
left = intervals[i][0]
right = intervals[i][1]
if left > prev_right:
result.append((prev_left, prev_right))
prev_left = left
prev_right = right
elif right > prev_right:
prev_right = right
result.append((prev_left, prev_right))
return result
Java Solution:
public static List<int[]> mergeInterval(int[][] l1, int[][] l2) {
int i =0, j =0;
List<int []> result = new LinkedList<>();
while(i < l1.length && j < l2.length){
if(l2[j][1] > l1[i][0]){
mergeWithResult(result, l1[i][0], l1[i][1]);
i++;
} else if(l1[i][1] > l2[j][0]){
mergeWithResult(result, l2[j][0], l2[j][1]);
j++;
}
}
while (i < l1.length){
mergeWithResult(result, l1[i][0], l1[i][1]);
i++;
}
while (j < l2.length){
mergeWithResult(result, l2[j][0], l2[j][1]);
j++;
}
return result;
}
private static void mergeWithResult(List<int[]> result, int e1, int e2) {
if(result.isEmpty())
result.add(new int[]{e1,e2});
else {
int [] ar = result.get(result.size()-1);
if(ar[1] < e1){
result.add(new int[]{e1,e2});
} else {
int[] newAr = new int[2];
newAr[0] = Integer.min(ar[0], e1);
newAr[1] = Integer.max(ar[1], e2);
result.remove(result.size() - 1);
result.add(newAr);
}
}
}
Some answers don't handle the more complext scenarios where one element may overlap multiple elements in the other list.
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
class MergeRanges {
static Range range(int start, int end) {
return new Range(start, end);
}
static class Range {
final int start;
final int end;
Range(int start, int end) {
if (end <= start) {
throw new IllegalArgumentException(end +" <= "+ start);
}
this.start = start;
this.end = end;
}
public boolean equals(Object other) {
Range rother = (Range)other;
return rother.start == this.start && rother.end == this.end;
}
public String toString() {
return "[" + start +", "+end+"]";
}
/**
*
* @param r
* @return -1 if this object is lesser than r
* @return 1 if this range is greater than r
* @return 0 if this range overlaps with r
*
*/
public int compareTo(Range r) {
if (this.end < r.start) {
return -1;
} else if (this.start > r.end) {
return 1;
}
//overlap
return 0;
}
public Range merge(Range r) {
return new Range(
Math.min(this.start, r.start),
Math.max(this.end, r.end)
);
}
}
static class DequeueArray {
final Range[] array;
int idx = 0;
DequeueArray(Range[] array) {
this.array = array;
}
boolean hasMore() {
return idx < (array.length);
}
Range peek() {
if (hasMore()) {
Range result = array[idx];
return result;
}
throw new IllegalStateException();
}
Range dequeue() {
Range result = peek();
idx++;
return result;
}
}
static Range[] merge(Range[] rangeList1, Range[] rangeList2) {
List<Range> result = new LinkedList<>();
DequeueArray dr1 = new DequeueArray(rangeList1);
DequeueArray dr2 = new DequeueArray(rangeList2);
Range r1=null, r2=null;
while (dr1.hasMore() || dr2.hasMore()) {
if (r1==null && dr1.hasMore()) {
r1 = dr1.dequeue();
}
if (r2==null && dr2.hasMore()) {
r2 = dr2.dequeue();
}
if (r1 != null && r2 != null) {
int compare = r1.compareTo(r2);
switch (compare) {
case -1 :
result.add(r1);
r1 = null;
break;
case 1 :
result.add(r2);
r2 = null;
break;
case 0:
Range temp = r1.merge(r2);
if (r1.end > r2.end) {
r1 = temp;
r2 = null;
} else {
r1 = null;
r2 = temp;
}
break;
default:
throw new IllegalStateException("Invalid comparison: " +compare);
}
} else if (r1 != null) {
result.add(r1);
r1 = null;
} else if (r2 != null) {
result.add(r2);
r2 = null;
}
}
if (r1 != null) { result.add(r1); }
if (r2 != null) { result.add(r2); }
return result.toArray(new Range[result.size()]);
}
static void test(Range[] expected, Range[] actual) {
if (!Arrays.equals(expected, actual)) {
throw new IllegalStateException("Ranges are not equal\n\t"+
"Expected: "+Arrays.toString(expected)+"\n\t" +
"Actual: "+Arrays.toString(actual)
);
}
}
public static void main(String[] args) {
Range[] range1 = new Range[] {range(1,2), range(3,9)};
Range[] range2 = new Range[] {range(4,5), range(8,10), range(11,12)};
Range[] merge = merge(range1, range2);
test(
new Range[] {range(1,2), range(3,10), range(11,12)},
merge
);
System.out.println("Merge:\n\t1. " + Arrays.toString(range1)+"\n\t2. "+Arrays.toString(range2)+"\n\tResult: "+Arrays.toString(merge));
range1 = new Range[] {range(1,2), range(4,15)};
range2 = new Range[] {range(3,5), range(8,10), range(11,12)};
merge = merge(range1, range2);
test(
new Range[] {range(1,2), range(3,15)},
merge
);
System.out.println("Merge:\n\t1. " + Arrays.toString(range1)+"\n\t2. "+Arrays.toString(range2)+"\n\tResult: "+Arrays.toString(merge));
range1 = new Range[] {range(1,2), range(4,15)};
range2 = new Range[] {range(1,2), range(4,15)};
merge = merge(range1, range2);
test(
new Range[] {range(1,2), range(4,15)},
merge
);
System.out.println("Merge:\n\t1. " + Arrays.toString(range1)+"\n\t2. "+Arrays.toString(range2)+"\n\tResult: "+Arrays.toString(merge));
range1 = new Range[] {range(1,2), range(3,5), range(8,12)};
range2 = new Range[] {range(2,15)};
merge = merge(range1, range2);
test(
new Range[] {range(1,15)},
merge
);
System.out.println("Merge:\n\t1. " + Arrays.toString(range1)+"\n\t2. "+Arrays.toString(range2)+"\n\tResult: "+Arrays.toString(merge));
}
}
- Guy November 12, 2018void merge(vector<pair<int,int> > &res, const pair<int,int> &toMerge){ if(res.empty() || toMerge.first > res.back().second){ res.push_back(toMerge); }else{ res.back().first = min(res.back().first,toMerge.first); res.back().second = max(res.back().second,toMerge.second); } } vector<pair<int,int> > mergeIntervals(const vector<pair<int,int> > &l1, const vector<pair<int,int> > &l2){ vector<pair<int,int> > result; for(int i = 0,j = 0; i < l1.size() || j < l2.size();){ if(i == l1.size()){ merge(result,l2[j++]); }else if(j == l2.size()){ merge(result,l1[i++]); }else{ if(l1[i].second < l2[j].first){ merge(result,l1[i++]); }else if(l2[j].second < l1[i].first){ merge(result,l2[j++]); }else{ merge(result,{min(l1[i].first,l2[j].first),max(l1[i].second,l2[j].second)}); i++; j++; } } } return result; }