给出一个区间的集合,请合并所有重叠的区间。
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
public class MySet {
int left;
int right;
public MySet(){
}
public MySet(int left,int right){
this.left = left;
this.right = right;
}
public int getLeft() {
return left;
}
public void setLeft(int left) {
this.left = left;
}
public int getRight() {
return right;
}
public void setRight(int right) {
this.right = right;
}
}
解法:
public static List<MySet> mergeSet(List<MySet> theSets) {
if (theSets == null || theSets.size() <= 1) {
return theSets;
}
List<MySet> result = new ArrayList<>();
theSets.sort((set1,set2)->{
return set1.getLeft() - set2.getLeft();
});
MySet mySet = theSets.get(0);
for (int i = 1; i < theSets.size(); i++){
if (!(mySet.getRight() < theSets.get(i).getLeft())){
mySet.setRight(Math.max(mySet.getRight(),theSets.get(i).getRight()));
} else {
result.add(mySet);
mySet = theSets.get(i);
}
}
//最后一定要将最后合并的元素加入到结果中。否则会丢失元素。
result.add(mySet);
return result;
}
public static void main(String[] args) {
MySet mySet1 = new MySet(1,4);
MySet mySet2 = new MySet(2,6);
MySet mySet3 = new MySet(8,10);
MySet mySet4 = new MySet(12,13);
MySet mySet5 = new MySet(16,19);
List<MySet> mySets = new LinkedList<>();
mySets.add(mySet1);
mySets.add(mySet2);
mySets.add(mySet3);
mySets.add(mySet4);
mySets.add(mySet5);
List<MySet> result = mergeSet(mySets);
System.out.println(JSONObject.toJSONString(result));
}
输出结果:
[{"left":1,"right":6},{"left":8,"right":10},{"left":12,"right":13},{"left":16,"right":19}]
网友评论