Facebook Interview Question Software Engineer Interns
Country: United States
Interview Type: Phone Interview
class Range:
def __init__(self, _min, _max):
self.min = _min
self.max = _max
def __str__(self):
return str(self.min) + "-" + str(self.max)
def __repr__(self):
return str(self)
def get_max(self):
return self.max
def get_min(self):
return self.min
def overlapping(self, other):
if (self.get_min() < other.get_min() < self.get_max()) \
or (self.get_min() < other.get_max() < self.get_max()) or \
(other.get_min() < self.get_min() < other.get_max()) \
or (other.get_min() < self.get_max() < other.get_max()):
return True
return False
def merge(self, other):
mmin = min(self.get_min(), other.get_min())
mmax = max(self.get_max(), other.get_max())
res = Range(mmin, mmax)
return res
def compare(self, other):
return cmp(self.min, other.min)
@staticmethod
def fix_array(index, array, retry=False):
if index > len(array):
return False
try:
left = array[index]
right = array[index + 1]
except Exception, e:
raise IndexError("fart")
if left.overlapping(right):
array.remove(left)
array.remove(right)
array.insert(index, left.merge(right))
if retry:
return Range.fix_array(index, array, retry=True)
return True
def merge(array1, array2):
result = []
result.extend(array1)
result.extend(array2)
result = sorted(result, cmp=Range.compare)
index = 0
while True:
try:
Range.fix_array(index, result, True)
index += 1
except IndexError, e:
return result
if __name__ == '__main__':
arr1 = [Range(3, 11), Range(17, 25), Range(58, 73)]
arr2 = [Range(6, 18), Range(40, 47)]
print merge(arr1, arr2)
arr1 = [Range(8, 13), Range(21, 32), Range(45, 60)]
arr2 = [Range(2, 9), Range(25, 46)]
print merge(arr1, arr2)
arr1 = [Range(1, 12), Range(26, 32), Range(51, 82)]
arr2 = [Range(9, 24), Range(49, 60), Range(75, 98)]
print merge(arr1, arr2)
private static ArrayList<Interval> mergeIntervals(ArrayList<Interval> a, ArrayList<Interval> b) {
ArrayList<Interval> result = new ArrayList<>();
int aIndex = 0;
int bIndex = 0;
while (aIndex < a.size() && bIndex < b.size()) {
Interval aInterval = a.get(aIndex);
Interval bInterval = b.get(bIndex);
if (!result.isEmpty() && (result.get(result.size() - 1).overlap(aInterval) || result.get(result.size() - 1).overlap(bInterval))) {
Interval previousResultInterval = result.get(result.size() - 1);
if (previousResultInterval.overlap(aInterval)) {
result.set(result.size() - 1, merge(previousResultInterval, aInterval));
aIndex++;
} else {
result.set(result.size() - 1, merge(previousResultInterval, bInterval));
bIndex++;
}
} else {
if (aInterval.before(bInterval)) {
result.add(aInterval);
aIndex++;
} else {
result.add(bInterval);
bIndex++;
}
}
}
while (aIndex < a.size()) {
result.add(a.get(aIndex));
aIndex++;
}
while (bIndex < b.size()) {
result.add(b.get(bIndex));
bIndex++;
}
return result;
}
private static Interval merge(Interval a, Interval b) {
if (a.overlap(b)) {
return new Interval(Math.min(a.start, b.start), Math.max(a.end, b.end));
}
return null;
}
private static class Interval {
final int start, end;
private Interval(int start, int end) {
this.start = start;
this.end = end;
}
private boolean overlap(Interval b) {
if ((start <= b.start && end >= b.start)
|| (b.start <= start && b.end >= start))
return true;
return false;
}
public boolean before(Interval other) {
return end < other.end;
}
@Override
public String toString() {
return "{" +
"start=" + start +
", end=" + end +
'}';
}
}
class Interval:
lower = None
upper = None
def __init__(self, lower, upper):
self.lower = lower
self.upper = upper
#Checks if the two intervals overlap with each other
def isOverlapping(self, ob):
if (ob.lower > self.lower and ob.lower < self.upper) \
or (ob.upper > self.lower and ob.upper < self.upper) :
return True
return False
#Pass in a set of interval elements to be merged
def merge(self, interval):
lowerBound = min(self.lower, interval.lower)
upperBound = max(self.upper, interval.upper)
return Interval(lowerBound, upperBound)
def findIntervalPosition(interval, arr1):
for i in xrange(len(arr1)-1,-1,-1):
if interval.lower > arr1[i].lower:
return i+1;
def mergeNewInterval(arr1, index):
lower = index - 1
upper = index + 1
while lower >= 0 or upper < len(arr1):
if lower >= 0:
if arr1[index].isOverlapping(arr1[lower]):
newInterval = arr1[index].merge(arr1[lower])
arr1.pop(index)
arr1.pop(lower)
arr1.insert(lower, newInterval)
index = index - 1
lower = lower - 1
upper = upper - 1
else:
lower = -1 #As soon as one lower element does not overlap, no other element
#below it will overlap. So no need to check
if upper < len(arr1):
if arr1[index].isOverlapping(arr1[upper]):
newInterval = arr1[index].merge(arr1[upper])
arr1.pop(upper)
arr1.pop(index)
arr1.insert(index, newInterval)
else:
upper = len(arr1) + 1
def main():
arr1 = [Interval(3,11), Interval(17,25), Interval(58,73)]
arr2 = [Interval(6,18), Interval(40,47)]
for interval in arr2:
#Insert the element into the right position in arr1
index = findIntervalPosition(interval, arr1)
arr1.insert(index, interval)
mergeNewInterval(arr1, index)
for interval in arr1:
print("({0}-{1})".format(interval.lower, interval.upper))
if __name__ == "__main__":
main()
class Interval:
lower = None
upper = None
def __init__(self, lower, upper):
self.lower = lower
self.upper = upper
#Checks if the two intervals overlap with each other
def isOverlapping(self, ob):
if (ob.lower > self.lower and ob.lower < self.upper) \
or (ob.upper > self.lower and ob.upper < self.upper) :
return True
return False
#Pass in a set of interval elements to be merged
def merge(self, interval):
lowerBound = min(self.lower, interval.lower)
upperBound = max(self.upper, interval.upper)
return Interval(lowerBound, upperBound)
def findIntervalPosition(interval, arr1):
for i in xrange(len(arr1)-1,-1,-1):
if interval.lower > arr1[i].lower:
return i+1;
def mergeNewInterval(arr1, index):
lower = index - 1
upper = index + 1
while lower >= 0 or upper < len(arr1):
if lower >= 0:
if arr1[index].isOverlapping(arr1[lower]):
newInterval = arr1[index].merge(arr1[lower])
arr1.pop(index)
arr1.pop(lower)
arr1.insert(lower, newInterval)
index = index - 1
lower = lower - 1
upper = upper - 1
else:
lower = -1 #As soon as one lower element does not overlap, no other element
#below it will overlap. So no need to check
if upper < len(arr1):
if arr1[index].isOverlapping(arr1[upper]):
newInterval = arr1[index].merge(arr1[upper])
arr1.pop(upper)
arr1.pop(index)
arr1.insert(index, newInterval)
else:
upper = len(arr1) + 1
def main():
arr1 = [Interval(3,11), Interval(17,25), Interval(58,73)]
arr2 = [Interval(6,18), Interval(40,47)]
for interval in arr2:
#Insert the element into the right position in arr1
index = findIntervalPosition(interval, arr1)
arr1.insert(index, interval)
mergeNewInterval(arr1, index)
for interval in arr1:
print("({0}-{1})".format(interval.lower, interval.upper))
if __name__ == "__main__":
main()
class Interval:
lower = None
upper = None
def __init__(self, lower, upper):
self.lower = lower
self.upper = upper
#Checks if the two intervals overlap with each other
def isOverlapping(self, ob):
if (ob.lower > self.lower and ob.lower < self.upper) \
or (ob.upper > self.lower and ob.upper < self.upper) :
return True
return False
#Pass in a set of interval elements to be merged
def merge(self, interval):
lowerBound = min(self.lower, interval.lower)
upperBound = max(self.upper, interval.upper)
return Interval(lowerBound, upperBound)
#Find the correct position of the new interval
def findIntervalPosition(interval, arr1):
for i in xrange(len(arr1)-1,-1,-1):
if interval.lower > arr1[i].lower:
return i+1;
#Merge all elements with which this new interval overlaps with
def mergeNewInterval(arr1, index):
lower = index - 1
upper = index + 1
while lower >= 0 or upper < len(arr1):
if lower >= 0:
if arr1[index].isOverlapping(arr1[lower]):
newInterval = arr1[index].merge(arr1[lower])
arr1.pop(index)
arr1.pop(lower)
arr1.insert(lower, newInterval)
index = index - 1
lower = lower - 1
upper = upper - 1
else:
lower = -1 #As soon as one lower element does not overlap, no other element
#below it will overlap. So no need to check
if upper < len(arr1):
if arr1[index].isOverlapping(arr1[upper]):
newInterval = arr1[index].merge(arr1[upper])
arr1.pop(upper)
arr1.pop(index)
arr1.insert(index, newInterval)
else:
upper = len(arr1) + 1
def main():
arr1 = [Interval(3,11), Interval(17,25), Interval(58,73)]
arr2 = [Interval(6,18), Interval(40,47)]
for interval in arr2:
#Insert the element into the right position in arr1
index = findIntervalPosition(interval, arr1)
arr1.insert(index, interval)
mergeNewInterval(arr1, index)
for interval in arr1:
print("({0}-{1})".format(interval.lower, interval.upper))
if __name__ == "__main__":
main()
This can be done in O(n) time. Keep reading from each array. Either the tow ranges are mutually exclusive. if exclusive find the smallest range and merge it with result array. Note you have to merge because it is possible that the new entry overlaps with previous entry in result. If the two entries read from the two arrays overlap and form a new overlap entry and merge it with result array.
Sample code:
{
#include "stdafx.h"
#include "vector"
struct entry
{
int start;
int end;
};
bool overlapping(struct entry entry1, struct entry entry2)
{
if ((entry1.start < entry2.start) && (entry1.end < entry2.start))
return false;
if ((entry1.start > entry2.end) && (entry1.end > entry2.end))
return false;
return true;
}
bool smaller(struct entry entry1, struct entry entry2)
{
if ((entry1.start < entry2.start) && (entry1.end < entry2.start))
return true;
return false;
}
void mergeToResult(std::vector<struct entry>& result, struct entry tempEntry)
{
if (result.size() == 0)
{
result.push_back(tempEntry);
return;
}
else
{
if (!overlapping(result[result.size() - 1], tempEntry))
{
if (smaller(result[result.size() - 1], tempEntry))
result.push_back(tempEntry);
//probably not needed, but can be there
else
{
struct entry tempEntry2 = result[result.size() - 1];
result.pop_back();
result.push_back(tempEntry);
result.push_back(tempEntry2);
}
}
else
{
struct entry tempEntry3;
struct entry tempEntry2 = result[result.size() - 1];
if (tempEntry.start <= tempEntry2.start)
tempEntry3.start = tempEntry.start;
else
tempEntry3.start = tempEntry2.start;
if (tempEntry.end >= tempEntry2.end)
tempEntry3.end = tempEntry.end;
else
tempEntry3.end = tempEntry2.end;
result.pop_back();
result.push_back(tempEntry3);
}
}
return;
}
int _tmain(int argc, _TCHAR* argv[])
{
std::vector<struct entry> arr1 = { { 3, 11 }, { 17, 25 }, { 58, 73 } };
std::vector<struct entry> arr2 = { { 6,18 }, { 40,47 } };
std::vector<struct entry> result = {};
int len1 = arr1.size();
int len2 = arr2.size();
int read1 = 0;
int read2 = 0;
while ((len1 > read1) && (len2 > read2))
{
if (!overlapping(arr1[read1], arr2[read2]))
{
if (smaller(arr1[read1], arr2[read2]))
{
mergeToResult(result, arr1[read1]);
read1++;
}
else
{
mergeToResult(result, arr2[read2]);
read2++;
}
}
else
{
struct entry tempEntry;
if (arr1[read1].start <= arr2[read2].start)
tempEntry.start = arr1[read1].start;
else
tempEntry.start = arr2[read2].start;
if (arr1[read1].end >= arr2[read2].end)
tempEntry.end = arr1[read1].end;
else
tempEntry.end = arr2[read2].end;
mergeToResult(result, tempEntry);
read1++;
read2++;
}
}
//fill remaining elements
if (read1 < len1)
{
while (read1 < len1)
{
mergeToResult(result, arr1[read1]);
read1++;
}
}
else
{
while (read2 < len2)
{
mergeToResult(result, arr2[read2]);
read2++;
}
}
//print result
int readIdx = 0;
while (readIdx < result.size())
{
printf("%d - %d", result[readIdx].start, result[readIdx].end);
printf("\n");
readIdx++;
}
return 0;
}}
#include "stdafx.h"
#include "vector"
struct entry
{
int start;
int end;
};
bool overlapping(struct entry entry1, struct entry entry2)
{
if ((entry1.start < entry2.start) && (entry1.end < entry2.start))
return false;
if ((entry1.start > entry2.end) && (entry1.end > entry2.end))
return false;
return true;
}
bool smaller(struct entry entry1, struct entry entry2)
{
if ((entry1.start < entry2.start) && (entry1.end < entry2.start))
return true;
return false;
}
void mergeToResult(std::vector<struct entry>& result, struct entry tempEntry)
{
if (result.size() == 0)
{
result.push_back(tempEntry);
return;
}
else
{
if (!overlapping(result[result.size() - 1], tempEntry))
{
if (smaller(result[result.size() - 1], tempEntry))
result.push_back(tempEntry);
//probably not needed, but can be there
else
{
struct entry tempEntry2 = result[result.size() - 1];
result.pop_back();
result.push_back(tempEntry);
result.push_back(tempEntry2);
}
}
else
{
struct entry tempEntry3;
struct entry tempEntry2 = result[result.size() - 1];
if (tempEntry.start <= tempEntry2.start)
tempEntry3.start = tempEntry.start;
else
tempEntry3.start = tempEntry2.start;
if (tempEntry.end >= tempEntry2.end)
tempEntry3.end = tempEntry.end;
else
tempEntry3.end = tempEntry2.end;
result.pop_back();
result.push_back(tempEntry3);
}
}
return;
}
int _tmain(int argc, _TCHAR* argv[])
{
std::vector<struct entry> arr1 = { { 3, 11 }, { 17, 25 }, { 58, 73 } };
std::vector<struct entry> arr2 = { { 6,18 }, { 40,47 } };
std::vector<struct entry> result = {};
int len1 = arr1.size();
int len2 = arr2.size();
int read1 = 0;
int read2 = 0;
while ((len1 > read1) && (len2 > read2))
{
if (!overlapping(arr1[read1], arr2[read2]))
{
if (smaller(arr1[read1], arr2[read2]))
{
mergeToResult(result, arr1[read1]);
read1++;
}
else
{
mergeToResult(result, arr2[read2]);
read2++;
}
}
else
{
struct entry tempEntry;
if (arr1[read1].start <= arr2[read2].start)
tempEntry.start = arr1[read1].start;
else
tempEntry.start = arr2[read2].start;
if (arr1[read1].end >= arr2[read2].end)
tempEntry.end = arr1[read1].end;
else
tempEntry.end = arr2[read2].end;
mergeToResult(result, tempEntry);
read1++;
read2++;
}
}
//fill remaining elements
if (read1 < len1)
{
while (read1 < len1)
{
mergeToResult(result, arr1[read1]);
read1++;
}
}
else
{
while (read2 < len2)
{
mergeToResult(result, arr2[read2]);
read2++;
}
}
//print result
int readIdx = 0;
while (readIdx < result.size())
{
printf("%d - %d", result[readIdx].start, result[readIdx].end);
printf("\n");
readIdx++;
}
return 0;
}
public List<Tuple<int, int>> Merge(List<Tuple<int, int>> l1, List<Tuple<int, int>> l2)
{
if (l1 == null && l2 == null)
return null;
if (l1 == null && l2.Count > 0)
return l2;
if (l2 == null && l1.Count > 0)
return l1;
var result = new List<Tuple<int, int>>();
int i = l1[0].Item1 < l2[0].Item1 ? 1 : 0;
int j = l2[0].Item1 < l1[0].Item1 ? 1 : 0; ;
Tuple<int, int> p = i == 1 ? l1[0] : l2[0];
Tuple<int, int> curr;
while (i < l1.Count || j < l2.Count)
{
if (i < l1.Count && j < l2.Count)
curr = (l1[i].Item1 < l2[j].Item1) ? l1[i++] : l2[j++];
else
curr = (i < l1.Count) ? l1[i++] : l2[j++];
if (curr.Item1 < p.Item2)
p = Tuple.Create(p.Item1, Math.Max(p.Item2, curr.Item2));
else
{
result.Add(p);
p = curr;
}
}
result.Add(p);
return result;
}
public class MergeIntervals {
static int[][] arr1 = new int[][] { { 3, 11 }, { 17, 25 }, { 58, 73 } };
static int[][] arr2 = new int[][] { { 6, 18 }, { 40, 47 } };
static int[][] arr3 = new int[arr1.length + arr2.length][];
/**
* @param args
*/
public static void main(String[] args) {
int i = 0;
int j = 0;
int k = 0;
int[] intersectionCheckInterval = null;
boolean isActiveIndexI = false; // This will tell with which array, we
// need to check
// intersection. This is useful in else case only when we already have
// an intersection
while (i < arr1.length && j < arr2.length) {
// If there was no previously known intersection to check current
// intervals with
if (intersectionCheckInterval == null) {
intersectionCheckInterval = getIntersectingInterval(arr1[i][0],
arr1[i][1], arr2[j][0], arr2[j][1]);
// If i and j do not intersect, select smaller interval and put
// into result array
if (intersectionCheckInterval == null) {
if (arr1[i][0] < arr2[j][0]) {
arr3[k++] = arr1[i++];
} else {
arr3[k++] = arr2[j++];
}
} else {
// If i and j intersect, we move ahead in i or j based on
// which
// interval had lesser high value
if (intersectionCheckInterval[1] == arr1[i][1]) {
j++;
isActiveIndexI = false;
} else {
i++;
isActiveIndexI = true;
}
}
} else {
// If we already have an intersection then
int[] temp = intersectionCheckInterval;
if (isActiveIndexI) {
intersectionCheckInterval = getIntersectingInterval(
intersectionCheckInterval[0],
intersectionCheckInterval[1], arr1[i][0],
arr1[i][1]);
if (intersectionCheckInterval == null) {
arr3[k++] = temp;
j++;
} else {
if (intersectionCheckInterval[1] == arr1[i][1]) {
j++;
isActiveIndexI = false;
} else {
i++;
isActiveIndexI = true;
}
}
} else {
intersectionCheckInterval = getIntersectingInterval(
intersectionCheckInterval[0],
intersectionCheckInterval[1], arr2[j][0],
arr2[j][1]);
if (intersectionCheckInterval == null) {
arr3[k++] = temp;
i++;
} else {
if (intersectionCheckInterval[1] == arr2[j][1]) {
i++;
isActiveIndexI = true;
} else {
j++;
isActiveIndexI = false;
}
}
}
}
}
if (i != arr1.length && j == arr2.length) {
while(i != arr1.length){
arr3[k++] = arr1[i++];
}
} else if (i == arr1.length && j != arr2.length) {
while(j != arr2.length){
arr3[k++] = arr2[j++];
}
}
for(int p=0;p<k;p++) {
System.out.println(arr3[p][0]+":"+arr3[p][1]);
}
}
static boolean isIntersecting(int low1, int high1, int low2, int high2) {
if (low1 >= low2 && low1 <= high2)
return true;
if (low2 >= low1 && low2 <= high1)
return true;
return false;
}
static int[] getIntersectingInterval(int low1, int high1, int low2,
int high2) {
int[] intersectInterval = null;
if (isIntersecting(low1, high1, low2, high2)) {
intersectInterval = new int[2];
intersectInterval[0] = Math.min(low1, low2);
intersectInterval[1] = Math.max(high1, high2);
}
return intersectInterval;
}
}
// C#
using System.Collections.Generic;
class Program
{
static void Main(string[] args)
{
Interval[] array1 = {
new Interval { Lower = 3, Upper = 11 },
new Interval { Lower = 17, Upper = 25 },
new Interval { Lower = 58, Upper = 73 } };
Interval[] array2 = {
new Interval { Lower = 6, Upper = 18 },
new Interval { Lower = 40, Upper = 47 }};
foreach (Interval r in Merge(array1, array2))
System.Console.Write("[" + r.Lower.ToString() + ", " + r.Upper.ToString() + "] ");
}
static Interval[] Merge(Interval[] array1, Interval[] array2)
{
List<Interval> result = new List<Interval>();
int i1, i2;
Interval currentInterval = new Interval(), selectedInterval = new Interval();
for (i1 = 0, i2 = 0; i1 < array1.Length || i2 < array2.Length;)
{
if (i1 < array1.Length && (i2 == array2.Length || array1[i1].Lower < array2[i2].Lower))
{
selectedInterval = array1[i1];
++i1;
}
else if (i2 < array2.Length && (i1 == array1.Length || array2[i2].Lower <= array1[i1].Lower))
{
selectedInterval = array2[i2];
++i2;
}
if (currentInterval.Upper >= selectedInterval.Lower)
{
if (currentInterval.Upper < selectedInterval.Upper)
currentInterval.Upper = selectedInterval.Upper;
}
else
{
result.Add(currentInterval);
currentInterval = selectedInterval;
}
}
result.Add(currentInterval);
result.RemoveAt(0);
return result.ToArray();
}
}
struct Interval
{
public int Lower;
public int Upper;
}
//Using LinkedLists with worst case time complexity of O(N+M) and space complexity //O(N+M)
public class IntervalOperations
{
public static Interval mergeIntervals(Interval a,Interval b)throws NullPointerException{
if(a==null||b==null)
{
throw new NullPointerException
}
Interval i=a;
Interval prevA=a;
Interval j=b;
Interval prevB=b;
Interval result;
Interval c;
if(a.start<=b.start)
{
result=i;
c=i;
prevA=i;
i=i.next;
}else
{
result=j;
c=j;
prevB=j;
j=j.next;
}
c.next=null;
while(i!=null && j!=null){
if(i.start<=j.start)
{
if(isOverlap(c,i))
{
c.start=Math.min(c.start,i.start);
c.end=Math.max(c.end,i.end);
prevA=i;
i=i.next;
}else{
prevA.next=null;
c.next=i;
c=c.next;
i=i.next;
c.next=null;
}
}else{
if(isOverlap(c,j))
{
c.start=Math.min(c.start,j.start);
c.end=Math.max(c.end,j.max);
prevB=j;
j=j.next;
}
prevB.next=null;
c.next=j;
c=c.next;
j=j.next;
c.next=null;
}
}
while(j!=null)
{
if(isOverlap(c,j))
{
c.start=Math.min(c.start,j.start);
c.end=Math.max(c.end,j.end);
prevB=j;
j=j.next;
}else{
prevB.next=null;
c.next=j;
c=c.next;
j=j.next;
c.next=null;
}
}
while(i!=null)
{
if(isOverlap(c,i))
{
c.start=Math.min(c.start,i.start);
c.end=Math.max(c.end,i.end);
prevA=i;
i=i.next;
}else{
prevA.next=null;
c.next=i;
c=c.next;
i=i.next;
c.next=null;
}
}
return result;
}
private static boolean isOverlap(Interval x,Interval y)
{
if(x.end<y.start||y.end<x.start)
{
return false;
}
return true;
}
public class Interval{
int start;
int end;
Interval next;
public Interal(int s,int e)
{
start=s;
end=e;
}
}
public static void printInterval(Interval a)
{
while(a!=null)
{
System.out.print("start: " + a.start + ", end: " + a.end + "-")
a=a.next;
}
}
public static void Main(String[] args)
{
Interval i=new Interval(3,10);
Interval v=i;
v.next=new Interval(12,15);
v=v.next;
v.next=new Interval(21,25);
Interval j=new Interval(6,10);
v=j;
v.next=new Node(11,18);
Interval result=IntervalOperations.mergeIntervals(i,j);
IntervalOperations.printInterval(i);
IntervalOperations.printInteval(j);
IntervalOperations.printInterval(result);
}
}
class Range:
def __init__(self, _min, _max):
self.min = _min
self.max = _max
def __str__(self):
return str(self.min) + "-" + str(self.max)
def __repr__(self):
return str(self)
def get_max(self):
return self.max
def get_min(self):
return self.min
def overlapping(self, other):
if (self.get_min() < other.get_min() < self.get_max()) \
or (self.get_min() < other.get_max() < self.get_max()) or \
(other.get_min() < self.get_min() < other.get_max()) \
or (other.get_min() < self.get_max() < other.get_max()):
return True
return False
def merge(self, other):
mmin = min(self.get_min(), other.get_min())
mmax = max(self.get_max(), other.get_max())
res = Range(mmin, mmax)
return res
def compare(self, other):
return cmp(self.min, other.min)
@staticmethod
def fix_array(index, array, retry=False):
if index > len(array):
return False
try:
left = array[index]
right = array[index + 1]
except Exception, e:
raise IndexError("fart")
if left.overlapping(right):
array.remove(left)
array.remove(right)
array.insert(index, left.merge(right))
if retry:
return Range.fix_array(index, array, retry=True)
return True
def merge(array1, array2):
result = []
result.extend(array1)
result.extend(array2)
result = sorted(result, cmp=Range.compare)
index = 0
while True:
try:
Range.fix_array(index, result, True)
index += 1
except IndexError, e:
return result
if __name__ == '__main__':
arr1 = [Range(3, 11), Range(17, 25), Range(58, 73)]
arr2 = [Range(6, 18), Range(40, 47)]
print merge(arr1, arr2)
arr1 = [Range(8, 13), Range(21, 32), Range(45, 60)]
arr2 = [Range(2, 9), Range(25, 46)]
print merge(arr1, arr2)
arr1 = [Range(1, 12), Range(26, 32), Range(51, 82)]
arr2 = [Range(9, 24), Range(49, 60), Range(75, 98)]
print merge(arr1, arr2)
Here is the java version
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
* Testing
* Created by joubin on 2/14/16.
*/
public class Range {
int min;
int max;
public Range(int min, int max) {
this.min = min;
this.max = max;
}
public int getMin() {
return min;
}
public void setMin(int min) {
this.min = min;
}
public int getMax() {
return max;
}
public void setMax(int max) {
this.max = max;
}
public boolean doesMerge(Range other) {
return (this.getMin() <= other.getMin() && other.getMin() <= this.getMax()) ||
(this.getMin() <= other.getMax() && other.getMax() <= this.getMax());
}
public void merge(Range other) {
this.setMin(Math.min(this.getMin(), other.getMin()));
this.setMax(Math.max(this.getMax(), other.getMax()));
}
private boolean after(Range range) {
return this.getMax() < range.getMin();
}
@Override
public boolean equals(Object obj) {
if (!(obj instanceof Range)) {
return false;
}
Range other = (Range) obj;
return this.getMin() == other.getMin() && this.getMax() == other.getMax();
}
@Override
public String toString() {
return this.min + "-" + this.max;
}
private int compare(Range p2) {
if (this.equals(p2)) {
return 0;
} else {
if (this.getMax() < p2.getMin()) {
return -1;
} else if (this.getMax() > p2.getMax()) {
return 1;
}
}
return 0;
}
public static class RangeCollection {
private List<Range> ranges = new ArrayList<>();
public RangeCollection(ArrayList<Range> ranges) {
this.ranges.addAll(ranges);
}
private void addInPlace(Range range) {
int index = 0;
for (Range item : this.ranges) {
if (item.after(range)) {
index = this.ranges.indexOf(item);
} else {
break;
}
}
this.ranges.add(index + 1, range);
}
private void selfMerge() {
this.ranges.sort(Range::compare);
Range left = null;
Range right = null;
Iterator<Range> it = this.getRanges().iterator();
while (it.hasNext()) {
if (it.hasNext())
left = it.next();
if (it.hasNext())
right = it.next();
assert left != null;
assert right != null;
if (left.doesMerge(right)) {
left.merge(right);
this.ranges.remove(right);
it = ranges.iterator();
}
}
}
public List<Range> getRanges() {
return ranges;
}
public void addItem(Range range) {
for (Range item : this.ranges) {
if (item.doesMerge(range)) {
item.merge(range);
return;
}
}
addInPlace(range);
this.selfMerge();
}
public void addItems(List<Range> ranges) {
ranges.forEach(this::addItem);
}
@Override
public String toString() {
return "" + ranges;
}
}
public static void main(String[] args) {
ArrayList<Range> rangeList1 = new ArrayList<Range>() {{
add(new Range(3, 11));
add(new Range(17, 25));
add(new Range(58, 73));
}};
ArrayList<Range> rangeList2 = new ArrayList<Range>() {{
add(new Range(6, 18));
add(new Range(40, 47));
}};
RangeCollection collection = new RangeCollection(rangeList1);
collection.addItems(rangeList2);
System.out.println(collection);
rangeList1 = new ArrayList<Range>() {{
add(new Range(8, 13));
add(new Range(21, 32));
add(new Range(45, 60));
}};
rangeList2 = new ArrayList<Range>() {{
add(new Range(2, 9));
add(new Range(25, 46));
}};
collection = new RangeCollection(rangeList1);
collection.addItems(rangeList2);
collection.selfMerge();
System.out.println(collection);
rangeList1 = new ArrayList<Range>() {{
add(new Range(1, 12));
add(new Range(26, 32));
add(new Range(51, 82));
}};
rangeList2 = new ArrayList<Range>() {{
add(new Range(9, 24));
add(new Range(49, 60));
add(new Range(75, 98));
}};
collection = new RangeCollection(rangeList1);
collection.addItems(rangeList2);
collection.selfMerge();
System.out.println(collection);
rangeList1 = new ArrayList<Range>() {{
add(new Range(6, 14));
add(new Range(34, 46));
add(new Range(78, 89));
}};
rangeList2 = new ArrayList<Range>() {{
add(new Range(16, 23));
add(new Range(45, 52));
add(new Range(62, 71));
}};
collection = new RangeCollection(rangeList1);
collection.addItems(rangeList2);
collection.selfMerge();
System.out.println(collection);
}
}
Here is the code in c++:
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
class interval
{
public:
int start;
int end;
void set(int _start, int _end)
{
start=_start;
end=_end;
}
interval()
{
}
};
void merge_arrays_and_sort(interval a[10], interval b[10], interval sorted_res[20], int n, int m)
{
int co=0,i=0, j=0;
while(i<n && j<m)
{
if(a[i].start < b[j].start)
{
sorted_res[co]=a[i];
co++;
i++;
}
else
{
sorted_res[co]=b[j];
co++;
j++;
}
}
//left items in b
while(j<m)
{
sorted_res[co]=b[j];
j++;
co++;
}
//left items in a
while(i<n)
{
sorted_res[co]=a[i];
i++;
co++;
}
}
void merge_intervals(interval a, interval b, interval *new_interval)
{
interval bigger;
interval smaller;
if(a.start>b.start)
{
bigger.start=a.start;
bigger.end=a.end;
smaller.start=b.start;
smaller.end=b.end;
}
else
{
bigger.start=b.start;
bigger.end=b.end;
smaller.start=a.start;
smaller.end=a.end;
}
new_interval->start=smaller.start;
if(smaller.end>bigger.end)
{
new_interval->end=smaller.end;
}
else
{
new_interval->end=bigger.end;
}
}
bool overlap(interval a, interval b)
{
if(a.start<b.start)
{
if(b.start<a.end)
{
return true;
}
else
{
return false;
}
}
else if(a.start > b.start)
{
if(a.start>b.start)
{
if(a.start < b.end)
return true;
else
return false;
}
else
return false;
}
else //start equally at same minute
return true;
}
void combin_intervals(interval arr[20], interval res[20], int *co, int n)
{
*co=0;
int i=1;
interval current;
current.start=arr[0].start;
current.end=arr[0].end;
while(i<n)
{
if(overlap(current, arr[i])==true)
{
interval new_interval;
merge_intervals(current, arr[i], &new_interval);
current.start=new_interval.start;
current.end=new_interval.end;
i++;
}
else
{
res[*co]=current;
*co=*co+1;
current=arr[i];
i++;
}
}
//left item
res[*co]=current;
}
int main()
{
interval a[10];
interval b[10];
interval sorted_arr[20];
interval result[20];
int n=3, m=2, result_co=0;
a[0].set(3, 11);
a[1].set(17, 25);
a[2].set(58, 73);
b[0].set(6, 18);
b[1].set(40, 47);
//1-merge arrays and sort them
merge_arrays_and_sort(a, b, sorted_arr, n, m);
cout<<"Merged and Sorted array:\n";
for(int i=0; i<m+n; i++)
cout<<sorted_arr[i].start<<"-"<<sorted_arr[i].end<<", ";
//2-combin intervals
combin_intervals(sorted_arr, result, &result_co, m+n);
cout<<"\nFinal Result:\n";
for(int i=0; i<=result_co; i++)
cout<<result[i].start<<"-"<<result[i].end<<", ";
return 0;
}
# if possible merge tuple 't', otherwise insert 't' into the dictionary ('myData') of tuples
def mergeOrInsert(t, myData):
merge = False
for k in myData:
if k < t[0] and myData[k] > t[0]:
if t[1] > myData[k]:
myData[k] = t[1]
merge = True
break
if not merge:
myData[t[0]] = t[1]
def mergeXY(lhTuple1, lhTuple2):
myL = dict()
print(lhTuple1)
print(lhTuple2)
i = 0
j = 0
while True:
if i < len(lhTuple1) and j < len(lhTuple2):
n1 = lhTuple1[i]
n2 = lhTuple2[j]
if n1[0] < n2[0]:
nt = n1
i += 1
else:
nt = n2
j+= 1
else:
while i < len(lhTuple1):
mergeOrInsert(lhTuple1[i], myL)
i += 1
while j < len(lhTuple2):
mergeOrInsert(lhTuple2[j],myL)
j += 1
break
#break the while loop
merge = False
print(nt)
mergeOrInsert(nt, myL)
sL = sorted(myL.items(), key = lambda x: x[0])
print(sL)
x = [(3,8), (12, 19), (23, 45), (79, 99)]
y =[(6,18), (40, 65), (70, 101), (103, 110), (115,200)]
mergeXY(x, y)
SAMPLE OUTPUT:
[(3, 19), (23, 65), (70, 101), (103, 110), (115, 200)]
class Interval
{
public $start;
public $end;
public function __construct(array $pair)
{
$this->start = $pair[0];
$this->end = $pair[1];
}
}
function joinIntervals(array &$result, Interval $int)
{
if (count($result) == 0) {
$result[] = $int;
return;
}
$last = end($result);
if ($last instanceof Interval) {
if ($last->end < $int->start) $result[] = $int;
else $last->end = $int->end;
}
}
function task($list1, $list2)
{
if (!is_array($list1) || !is_array($list2)) throw new InvalidArgumentException();
if (count($list2) == 0) return $list1;
if (count($list1) == 0) return $list2;
$result = [];
$pos1 = $pos2 = 0;
while ($pos1 < count($list1) || $pos2 < count($list2)) {
if ($pos2 == count($list2) || $list1[$pos1][0] <= $list2[$pos2][0]) {
joinIntervals($result, new Interval($list1[$pos1]));
$pos1++;
} elseif ($pos1 == count($list2) || $list1[$pos1][0] > $list2[$pos2][0]) {
joinIntervals($result, new Interval($list2[$pos2]));
$pos2++;
}
}
return $result;
}
$list1 = [[3, 11], [17, 25], [26, 27], [29, 41], [58, 73]];
$list2 = [[6, 18], [40, 47]];
print_r(task($list1, $list2));
class Interval
{
public $start;
public $end;
public function __construct(array $pair)
{
$this->start = $pair[0];
$this->end = $pair[1];
}
}
function joinIntervals(array &$result, Interval $int)
{
if (count($result) == 0) {
$result[] = $int;
return;
}
$last = end($result);
if ($last instanceof Interval) {
if ($last->end < $int->start) $result[] = $int;
else $last->end = $int->end;
}
}
function task($list1, $list2)
{
if (!is_array($list1) || !is_array($list2)) throw new InvalidArgumentException();
if (count($list2) == 0) return $list1;
if (count($list1) == 0) return $list2;
$result = [];
$pos1 = $pos2 = 0;
while ($pos1 < count($list1) || $pos2 < count($list2)) {
if ($pos2 == count($list2) || $list1[$pos1][0] <= $list2[$pos2][0]) {
joinIntervals($result, new Interval($list1[$pos1]));
$pos1++;
} elseif ($pos1 == count($list2) || $list1[$pos1][0] > $list2[$pos2][0]) {
joinIntervals($result, new Interval($list2[$pos2]));
$pos2++;
}
}
return $result;
}
$list1 = [[3, 11], [17, 25], [26, 27], [29, 41], [58, 73]];
$list2 = [[6, 18], [40, 47]];
print_r(task($list1, $list2));
import java.io.*;
import java.util.*;
class Range {
private int min, max;
public Range(int min, int max) {
this.min = min;
this.max = max;
}
public int getMin() {
return min;
}
public int getMax() {
return max;
}
public void setMin(int min) {
this.min = min;
}
public void setMax(int max) {
this.max = max;
}
}
class Solution {
public static List<Range> mergeRangesArrays(List<Range> arr1, List<Range> arr2) {
List<Range> result = new ArrayList<Range>();
Range newRange;
int arr1Index = 0, arr2Index = 0;
while(arr1Index < arr1.size() && arr2Index < arr2.size()) {
if (arr1.get(arr1Index).getMin() <= arr2.get(arr2Index).getMin()) {
if (arr1.get(arr1Index).getMax() >= arr2.get(arr2Index).getMin()) {
if (arr1.get(arr1Index).getMax() >= arr2.get(arr2Index).getMax()) {
newRange = new Range(arr1.get(arr1Index).getMin(), arr1.get(arr1Index).getMax());
} else {
newRange = new Range(arr1.get(arr1Index).getMin(), arr2.get(arr2Index).getMax());
}
arr1Index++;
arr2Index++;
result.add(newRange);
} else {
newRange = new Range(arr1.get(arr1Index).getMin(), arr1.get(arr1Index).getMax());
arr1Index++;
result.add(newRange);
}
} else {// (arr1[arr1Index].getMin() > arr2[arr2Index].getMin())
if (arr2.get(arr2Index).getMax() >= arr1.get(arr1Index).getMin()) {
if (arr1.get(arr1Index).getMax() >= arr2.get(arr2Index).getMax()) {
newRange = new Range(arr2.get(arr2Index).getMin(), arr1.get(arr1Index).getMax());
} else {
newRange = new Range(arr2.get(arr1Index).getMin(), arr2.get(arr2Index).getMax());
}
arr1Index++;
arr2Index++;
result.add(newRange);
} else {
newRange = new Range(arr2.get(arr2Index).getMin(), arr2.get(arr2Index).getMax());
arr2Index++;
result.add(newRange);
}
}
}
while (arr1Index < arr1.size()) {
result.add(arr1.get(arr1Index));
arr1Index++;
}
while (arr2Index < arr2.size()) {
result.add(arr2.get(arr2Index));
arr2Index++;
}
List<Range> actualResult = new ArrayList<Range>();
for (int i = 0; i < result.size(); i++) {
Range tmpRange = new Range(result.get(i).getMin(), result.get(i).getMax());
while (i < result.size() - 1 && tmpRange.getMax() >= result.get(i + 1).getMin()) {
tmpRange.setMax(result.get(i + 1).getMax());
i++;
}
actualResult.add(tmpRange);
}
return actualResult;
}
public static void main(String[] args) {
List<Range> arr1 = new ArrayList<Range>();
List<Range> arr2 = new ArrayList<Range>();
arr1.add(new Range(3, 11));
arr1.add(new Range(17, 25));
arr1.add(new Range(58, 73));
arr2.add(new Range(6, 18));
arr2.add(new Range(40, 47));
List<Range> result = mergeRangesArrays(arr1, arr2);
for (int i = 0; i < result.size(); i++) {
System.out.println("[" + result.get(i).getMin() + ", " + result.get(i).getMax() + "]");
}
}
}
Javascript: I wrote a version as if the ranges were strings
Arr1 = ["3-11", "17-25", "58-73"];
Arr2 = ["6-18", "40-47"];
function intersect(Arr1,Arr2){
arr = Arr1.concat(Arr2);
var notReady = true;
var index = 0;
var lastLength = 0;
while(notReady){
for(var i=0;i<arr.length;i++){
if(index !== i){
var f1 = Number(arr[index].match(/\b\d+/));
var l1 = Number(arr[index].match(/\-\d+/)[0].substring(1));
var f2 = Number(arr[i].match(/\b\d+/));
var l2 = Number(arr[i].match(/\-\d+/)[0].substring(1));
if(f2<f1 && l2>f1){
foundOne(index,i,arr);
break;
}else if(f1<f2 && l1>f2){
foundOne(index,i,arr);
break;
}else{
if(i===arr.length-1 && arr.length===lastLength) notReady=false;
}
}
}
}
function foundOne(index,i,arr){
var first = f1<f2 ? f1 : f2;
var last = l1>l2 ? l1 : l2;
arr[i] = first + "-" + last;
arr.splice(index,1);
lastLength = arr.length;
}
return arr.sort();
}
#!/usr/bin/perl
use Data::Dumper;
use strict;
#
# within range start_element < first < end_element AND new-range existing end_element < first
#
my @array1 = ([17..25],[3..11],[58..73]);
my @array2 = ([6..18],[0..47],[101..1000]);
my %set;
my %hash ;
my @set_define ;
my $count = 1;
foreach my $each_set ((@array1,@array2)) {
map {$hash{$_}++} @{$each_set};
}
my $temp ;
foreach my $keys (sort {$a<=>$b} keys %hash) {
if ($temp) {
my $diff = $keys - $temp ;
if ( $diff > 1) {
push @{$set{++$count}}, $keys ;
} else {
push @{$set{$count}}, $keys ;
}
} else {
push @{$set{$count}}, $keys ;
}
$temp = $keys;
}
foreach my $array (sort {$a<=>$b} keys %set) {
my $first = $set{$array}->[0];
my $last = $set{$array}->[-1];
push @set_define, [$first."..".$last];
}
map {print "[",@{$_},"] "; } @set_define;
O/P :- [0..47] [58..73] [101..1000]
It is the one of the easiest way to solve this algorithm, using associative array ( hash ).
#!/usr/bin/perl
use Data::Dumper;
use strict;
#
# within range start_element < first < end_element AND new-range existing end_element < first
#
my @array1 = ([17..25],[3..11],[58..73]);
my @array2 = ([6..18],[0..47],[101..1000]);
## O/P array3 = ([3..25],[40..47],[58..73]);
my %set;
my %hash ;
my @set_define ;
my $count = 1;
foreach my $each_set ((@array1,@array2)) {
map {$hash{$_}++} @{$each_set};
}
my $temp ;
foreach my $keys (sort {$a<=>$b} keys %hash) {
if ($temp) {
my $diff = $keys - $temp ;
if ( $diff > 1) {
push @{$set{++$count}}, $keys ;
} else {
push @{$set{$count}}, $keys ;
}
} else {
push @{$set{$count}}, $keys ;
}
$temp = $keys;
}
foreach my $array (sort {$a<=>$b} keys %set) {
my $first = $set{$array}->[0];
my $last = $set{$array}->[-1];
push @set_define, [$first."..".$last];
}
map {print "[",@{$_},"] "; } @set_define;
If we implement this using Interval-Tree would have been more generic a solution.
#include <stdio.h>
typedef struct _Interval{
int low;
int high;
}interval;
bool doOverlap(interval i, interval j){
return (i.low <= j.high && j.low <= i.high) ? true: false;
}
void findAllOverlaps(interval *arr, interval j, int size, interval *ret, int *ii){
for (int i = 0; i < size; i++){
if (doOverlap(arr[i], j))
ret[(*ii)++] = arr[i];
}
}
int main(){
interval arr1[3] = { { 3, 11 }, { 17, 25 }, { 58, 73 } };
interval arr2[2] = { { 6, 18 }, { 40, 47 } };
int next = 0;
interval temp[3];
for (int jj = 0; jj < 2; jj++)
{
int j = 0;
findAllOverlaps(arr1, arr2[jj], 3, temp, &j);
next += j;
if (j > 0){
arr1[jj].low = temp[0].low;
arr1[jj].high = temp[j - 1].high;
}
else arr1[jj] = arr2[jj];
}
for (int jj = next; jj < SIZE; jj++)
arr1[jj] = arr1[jj];
for (int i = 0; i < SIZE; i++)
printf("%d-%d ",arr1[i].low, arr1[i].high);
return 0;
}
Keep merging data from both list , insert first interval with lesser start
Arr1 = [3-11, 17-25, 58-73];
Arr2 = [6-18, 40-47];
Arr3 = 3-11,
Arr1 = 17-25,58-73
Arr2 = 6-18,40-47
when inserting next interval check if curlow <= A3.high && curhigh >A3.high, if so update A3.high, else add (curlow-curhigh) to list
A3 = 3,18
Arr1 = 17-25,58-73
Arr2 = 40-47
A3 = 3,25
Arr1 = 58-73
Arr2 = 40-47
A3 = 3,25, 40-47, 58-73
Shorter solution in python using generators:
def mergeit(list1, list2):
p1, p2 = 0, 0
while p1 < len(list1) or p2 < len(list2):
if p2 >= len(list2) or list1[p1] < list2[p2]:
yield list1[p1]
p1 += 1
else:
yield list2[p2]
p2 += 1
def merge(list1, list2):
current = None
for seg in mergeit(list1, list2):
if current is None:
current = seg
else:
if seg[0] > current[1]:
yield current
current = seg
elif seg[1] > current[1]:
current = (current[0], seg[1])
else:
pass
if current is not None:
yield current
print(list(merge([(3,11), (17,25), (58,73)], [(6,18),(40,47)])))
# Output: [(3, 25), (40, 47), (58, 73)]
python version
def merge(left, right):
p_left = 0
p_right = 0
result = []
if left[p_left][0] <= right[p_right][0]:
start = left[p_left][0]
end = left[p_left][1]
p_left +=1
else:
start = right[p_right][0]
end = right[p_right][1]
p_right += 1
while p_left < len(left) or p_right < len(right):
if p_left < len(left) and start <= left[p_left][0] and end >= left[p_left][0]:
end = max(end, left[p_left][1])
p_left += 1
elif p_right < len(right) and start <= right[p_right][0] and end >= right[p_right][0]:
end = max(end, right[p_right][1])
p_right += 1
else:
result.append((start, end))
if p_left < len(left) and p_right < len(right):
start = min(left[p_left][0], right[p_right][0])
end = left[p_left][1] if start == left[p_left][0] else right[p_right][1]
elif p_left < len(left):
start = left[p_left][0]
end = left[p_left][1]
else:
start = right[p_right][0]
end = right[p_right][1]
result.append((start, end))
return result
#include <iostream>
#include <vector>
using std::cout;
using std::vector;
// arr1 = [ 3-11, 17-25, 58-73 ]
// arr2 = [ 6-18, 40-47 ]
vector<int> * merge_arrays(const vector<int>& arr1, const vector<int>& arr2) {
vector<int> * merged = new vector<int>();
auto i = arr1.begin();
auto j = arr2.begin();
while (i != arr1.end() || j != arr2.end()) {
if (j == arr2.end() || *i < *j) {
merged->push_back(*i);
++i;
} else if (i == arr1.end() || *j < *i) {
merged->push_back(*j);
++j;
} else {
merged->push_back(*i);
++i;
++j;
}
}
return merged;
}
Simple solution using two pointers.
Time Complexity: O(n). Space complexity: O(1) (no extra memory except the return merged intervals).
struct Interval{
int begin, end;
Interval(int begin, int end){
this->begin = begin;
this->end = end;
}
};
void merge_interval(vector<Interval*> &intervals, Interval* to_be_merged){
int n = (int) intervals.size();
if(n == 0){
intervals.push_back(to_be_merged);
return;
}
if(to_be_merged->begin > intervals[n-1]->end){
intervals.push_back(to_be_merged);
}else{
intervals[n-1]->end = max(intervals[n-1]->end, to_be_merged->end);
}
}
vector<Interval*> merge_intervals(vector<Interval*> &intervals1, vector<Interval*> &intervals2){
if(intervals1.size() == 0){
return intervals2;
}
if(intervals2.size() == 0){
return intervals1;
}
vector<Interval*> merged_intervals;
// now we are sure that none of them is empty.
int i=0, j =0;
while(i < intervals1.size() && j < intervals2.size() ){
if(intervals1[i]->begin < intervals2[j]->begin){
merge_interval(merged_intervals, intervals1[i++]);
}else{
merge_interval(merged_intervals, intervals2[j++]);
}
}
while(i < intervals1.size()){
merge_interval(merged_intervals, intervals1[i++]);
}
while(j < intervals2.size()){
merge_interval(merged_intervals, intervals2[j++]);
}
return merged_intervals;
}
def merge(arr1, arr2):
#return Array
arr3 = []
while len(arr1) > 0 and len(arr2) > 0:
a1 = [int(x) for x in arr1[0].split("-")]
a2 = [int(x) for x in arr2[0].split("-")]
if a1[0] < a2[0]:
m = a1
del arr1[0]
else:
m = a2
del arr2[0]
if len(arr3) == 0:
arr3.append(m)
else:
if m[0] < arr3[-1][1]:
arr3[-1][1] = m[1]
else:
arr3.append(m)
#
if len(arr1)>0:
a1 = [int(x) for x in arr1[0].split("-")]
if len(arr3) > 0 and a1[0] < arr3[-1][1] :
arr3[-1][1] = a1[1]
del arr1[0]
if len(arr1) > 0:
for a1 in arr1:
arr3.append([int(x) for x in arr1[0].split("-")])
else:
a2 = [int(x) for x in arr2[0].split("-")]
if len(arr3) > 0 and a2[0] < arr3[-1][1]:
arr3[-1][1] = a2[1]
del arr2[0]
if len(arr2) > 0:
for a2 in arr2:
arr3.append([int(x) for x in arr2[0].split("-")])
for a3 in arr3:
a3 = str(a3[0])+"-"+str(a3[1])
return arr3
function merge(intervals1, intervals2) {
const ascendingByStart = []
let i = 0
let j = 0
while (i < intervals1.length || j < intervals2.length) {
if (i === intervals1.length) {
ascendingByStart.push(intervals2[j++])
} else if (j === intervals2.length) {
ascendingByStart.push(intervals1[i++])
} else if (intervals1[i][0] < intervals2[j][0]) {
ascendingByStart.push(intervals1[i++])
} else {
ascendingByStart.push(intervals2[j++])
}
}
const mergedIntervals = []
let start = null
let end = null
for (const interval of ascendingByStart) {
if (start === null && end === null) {
start = interval[0]
end = interval[1]
continue
}
if (start < interval[0] && interval[0] < end) {
end = Math.max(interval[1], end)
} else {
mergedIntervals.push([start, end])
start = interval[0]
end = interval[1]
}
}
if (start !== null && end !== null) {
mergedIntervals.push([start, end])
}
return mergedIntervals
}
// some overlap, no full containment
console.log(merge(
[[3, 11], [17, 25], [58, 73]],
[[6, 18], [40, 47]]
))
// some intervals fully contained in others
console.log(merge(
[[4, 5], [7, 9], [10, 15]],
[[3, 8], [11, 13]]
))
No need for sorting, similar to merging sorted arrays in merge sort just we need to consider ranges
package com.example.test;
import java.util.ArrayList;
import java.util.List;
public class MergeSortedArrays {
class Range {
int min;
int max;
public Range(int min, int max) {
this.min = min;
this.max = max;
}
}
public List<Range> mergeSortedArrays(List<Range> arr1, List<Range> arr2) {
if(arr1 == null || arr2 == null)
return null;
if(arr1.size() == 0)
return arr2;
if(arr2.size() == 0)
return arr1;
List<Range> result = new ArrayList<Range>();
int length1 = arr1.size();
int length2 = arr2.size();
Range lastNode = null;
int count = 0, i = 0, j = 0;
while(i < length1 && j < length2) {
Range current = null;
if(arr1.get(i).min < arr2.get(j).min) {
current = arr1.get(i);
i++;
}
else {
current = arr2.get(j);
j++;
}
if(lastNode != null) {
if(lastNode.max >= current.min) {
result.get(count-1).max = current.max;
continue;
}
}
result.add(current);
lastNode = current;
count++;
}
while(i < length1) {
result.add(arr1.get(i));
i++;
}
while(j < length2) {
result.add(arr2.get(j));
j++;
}
return result;
}
public static void main(String args[]) {
MergeSortedArrays mergeArray = new MergeSortedArrays();
List<Range> range1 = new ArrayList<Range>();
List<Range> range2 = new ArrayList<Range>();
range1.add(mergeArray.new Range(3,11));
range1.add(mergeArray.new Range(17,25));
range1.add(mergeArray.new Range(58,73));
range2.add(mergeArray.new Range(6,18));
range2.add(mergeArray.new Range(40,47));
List<Range> res = mergeArray.mergeSortedArrays(range1, range2);
if(res != null) {
for(Range r : res) {
System.out.println("["+r.min + "," + r.max+"]");
}
}
}
}
package com.example.test;
import java.util.ArrayList;
import java.util.List;
public class MergeSortedArrays {
class Range {
int min;
int max;
public Range(int min, int max) {
this.min = min;
this.max = max;
}
}
public List<Range> mergeSortedArrays(List<Range> arr1, List<Range> arr2) {
if(arr1 == null || arr2 == null)
return null;
if(arr1.size() == 0)
return arr2;
if(arr2.size() == 0)
return arr1;
List<Range> result = new ArrayList<Range>();
int length1 = arr1.size();
int length2 = arr2.size();
Range lastNode = null;
int count = 0, i = 0, j = 0;
while(i < length1 && j < length2) {
Range current = null;
if(arr1.get(i).min < arr2.get(j).min) {
current = arr1.get(i);
i++;
}
else {
current = arr2.get(j);
j++;
}
if(lastNode != null) {
if(lastNode.max >= current.min) {
result.get(count-1).max = current.max;
continue;
}
}
result.add(current);
lastNode = current;
count++;
}
while(i < length1) {
result.add(arr1.get(i));
i++;
}
while(j < length2) {
result.add(arr2.get(j));
j++;
}
return result;
}
public static void main(String args[]) {
MergeSortedArrays mergeArray = new MergeSortedArrays();
List<Range> range1 = new ArrayList<Range>();
List<Range> range2 = new ArrayList<Range>();
range1.add(mergeArray.new Range(3,11));
range1.add(mergeArray.new Range(17,25));
range1.add(mergeArray.new Range(58,73));
range2.add(mergeArray.new Range(6,18));
range2.add(mergeArray.new Range(40,47));
List<Range> res = mergeArray.mergeSortedArrays(range1, range2);
if(res != null) {
for(Range r : res) {
System.out.println("["+r.min + "," + r.max+"]");
}
}
}
}
It's quite a straightforward, No need to complicate it.
Logic: Use two pointers & a queue.
Steps:
1. Start each pointer from the start of the list.
2. If the queue is empty, compare the pointers such that
2.1 If the interval overlap, insert the new interval inside the queue and increment the pointers.
2.2 Insert the lower interval into the list and increment that pointer.
3. Compare both the pointers with the head of the queue. Dequeue & enqueue if required.
4. Repeat this process until all intervals are covered.
I have done a JavaScript solution that is O(n log n) due to the sort.
function getNonIntersetingArrayMerge(first, second) {
var workingItem;
var items = first.concat(second);
var results = [];
items.map(function (val, index, array) {
array[index] = val.split('-').map(Number);
});
items.sort(function (a, b) {
return a[0] - b[0];
});
workingItem = items.splice(0,1)[0];
while(items.length > 0) {
item = items.splice(0,1)[0];
if (item[0] < workingItem[1]) {
workingItem[1] = item[1];
continue;
}
results.push(workingItem);
workingItem = item;
}
results.push(workingItem);
results.map(function (val, index, array) {
array[index] = val.join('-');
});
return results;
}
var first = ['3-11', '17-25', '58-73'];
var second = ['6-18', '40-47'];
getNonIntersetingArrayMerge(first, second);
O(|arr1| + |arr2|) solution in java
static ArrayList<int[]> merge(int[][] arr1, int[][] arr2) {
ArrayList<int[]> result = new ArrayList<>();
boolean arr1Empty= arr1==null || arr1.length==0;
boolean arr2Empty= arr2==null || arr2.length==0;
if(arr1Empty && arr2Empty ) {
return result;
}else if ( arr1Empty) {
result.addAll(Arrays.asList(arr2));
return result;
}else if ( arr2Empty) {
result.addAll(Arrays.asList(arr1));
return result;
}
int i= 0, j= 0;
int start= -1, end = -1;
while( i<arr1.length && j < arr2.length){
if( arr1[i][0] < arr2[j][0] ) {
if(end < arr1[i][0]) {
if(start!=-1) {
result.add(new int[]{start, end});
}
start = arr1[i][0];
end = arr1[i][1];
}else{
end = arr1[i][1];
}
i++;
}else{
if(end < arr2[j][0]) {
if(start!=-1) {
result.add(new int[]{start, end});
}
start = arr2[j][0];
end = arr2[j][1];
}else{
end = arr2[j][1];
}
j++;
}
}
if(i<arr1.length || j<arr2.length) {
result.add(new int[]{start, end});
}
while( i<arr1.length ){
result.add(new int[]{arr1[i][0], arr1[i][1] });
i++;
}
while( j<arr2.length ){
result.add(new int[]{arr2[j][0], arr2[j][1]});
j++;
}
return result;
}
sorting and then using a stack
- kamrultopu February 13, 2016public ArrayList<Integer> MergeRangeArray(int[] arr1, int[] arr2){ ArrayList<Integer> list = new ArrayList<Integer>(); ArrayList<Info> arrInfo = new ArrayList<Info>(); Stack<Info> stack = new Stack<Info>(); for( int i = 0 ; i < arr1.length - 1;i+=2){ Info tempstart = new Info(arr1[i],'S'); Info tempEnd = new Info(arr1[i+1],'E'); arrInfo.add(tempstart); arrInfo.add(tempEnd); //System.out.println(tempstart + " " + tempEnd); } for( int i = 0 ; i < arr2.length - 1;i+=2){ Info tempstart = new Info(arr2[i],'S'); Info tempEnd = new Info(arr2[i+1],'E'); arrInfo.add(tempstart); arrInfo.add(tempEnd); } Collections.sort(arrInfo); //System.out.println(arrInfo.toString()); for( int i = 0 ; i < arrInfo.size();i++){ if( arrInfo.get(i).type == 'S'){ stack.push(arrInfo.get(i)); } else{ Info temp = stack.pop(); if( stack.isEmpty()){ list.add(temp.val); list.add(arrInfo.get(i).val); } } } return list; }