Merge K sorted interval lists into one sorted interval list. You need to merge overlapping intervals too.
Example
Example1
Input: [
[(1,3),(4,7),(6,8)],
[(1,2),(9,10)]
]
Output: [(1,3),(4,8),(9,10)]
Example2
Input: [
[(1,2),(5,6)],
[(3,4),(7,8)]
]
Output: [(1,2),(3,4),(5,6),(7,8)]
/**
* Definition of Interval:
* public classs Interval {
* int start, end;
* Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
public class Solution {
/**
* @param intervals: the given k sorted interval lists
* @return: the new sorted interval list
*/
public List<Interval> mergeKSortedIntervalLists(List<List<Interval>> intervals) {
// write your code here
List<Interval> ans = new ArrayList<>();
if (intervals == null || intervals.size() == 0) {
return ans;
}
return mergeHelper(0, intervals.size() - 1, intervals);
}
private List<Interval> mergeHelper(int start, int end, List<List<Interval>> intervals) {
if (start == end) {
return intervals.get(start);
}
int mid = start + (end - start) / 2;
List<Interval> left = mergeHelper(start, mid, intervals);
List<Interval> right = mergeHelper(mid + 1, end, intervals);
return mergeTwoLists(left, right);
}
private List<Interval> mergeTwoLists(List<Interval> list1, List<Interval> list2) {
int i = 0;
int j = 0;
Interval prev = null;
List<Interval> ans = new ArrayList<>();
while (i < list1.size() && j < list2.size()) {
Interval curr = null;
Interval v1 = list1.get(i);
Interval v2 = list2.get(j);
if (v1.start < v2.start) {
curr = v1;
prev = merge(ans, prev, curr);
i++;
} else {
curr = v2;
prev = merge(ans, prev, curr);
j++;
}
}
while (i < list1.size()) {
Interval curr = list1.get(i);
prev = merge(ans, prev, curr);
i++;
}
while (j < list2.size()) {
Interval curr = list2.get(j);
prev = merge(ans, prev, curr);
j++;
}
if (prev != null) {
ans.add(prev);
}
return ans;
}
private Interval merge(List<Interval> ans, Interval prev, Interval curr) {
if (prev == null) {
prev = curr;
return prev;
}
if (prev.end < curr.start) {
ans.add(prev);
prev = curr;
}
prev.end = Math.max(prev.end, curr.end);
return prev;
}
}
Modified Solution :
ReplyDeleteimport java.util.*;
class Interval
{
int start,end;
Interval(int start, int end)
{
this.start=start;
this.end=end;
}
public String toString()
{
return this.start + " " + this.end ;
}
}
class SortbyEnd implements Comparator
{
// Used for sorting in ascending order of
// roll number
public int compare(Interval a, Interval b)
{
return a.end - b.end;
}
}
class MyClass
{
public static void main(String args[]){
List list = new ArrayList();
//list.add(new Interval(1,2));list.add(new Interval(4,7));list.add(new Interval(1,3));list.add(new Interval(6,8));list.add(new Interval(9,10));
list.add(new Interval(1,2));list.add(new Interval(5,6));list.add(new Interval(3,4));list.add(new Interval(7,8));
Collections.sort(list, new SortbyEnd());
System.out.println(list);
test(list);
}
static void test(List list)
{
int a=0,b=0;
List ans = new ArrayList();
for(int i=0;i list.get(i+1).start)
{
a=list.get(i).start;
b=list.get(i+1).end;
ans.add(new Interval(a,b));
i+=1;
}
else{
ans.add(new Interval(list.get(i).start,list.get(i).end));
}
}
System.out.println(ans);
}
}