给定一个无重叠的,按照区间起点升序排列的区间列表,在列表中插入一个新区间,如果有原区间有重合,则合并,请返回插入后的区间列表。
数据范围:区间列表长度满足 , 区间的左右端点满足
import java.util.*; /* * public class Interval { * int start; * int end; * public Interval(int start, int end) { * this.start = start; * this.end = end; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param Intervals Interval类一维数组 * @param newInterval Interval类 * @return Interval类一维数组 */ public Interval[] insertInterval (Interval[] Intervals, Interval newInterval) { // write code here if(Intervals.length == 0){ return new Interval[]{newInterval}; } ArrayList<Interval> list = new ArrayList<>(); list.add(newInterval); for(int i = 0; i < Intervals.length; i++){ list.add(Intervals[i]); } // 先对所有区间按起点升序终点也升序进行二次排序,这样可以保证相同起点的区间,更大的区间在后面 Collections.sort(list, (a, b) -> a.start != b.start? a.start - b.start: a.end - b.end); // 用双端链表构建一个结果集 LinkedList<Interval> linkedlist = new LinkedList<>(); linkedlist.add(list.get(0)); for(int i = 1; i < list.size(); i++){ if(list.get(i).start <= linkedlist.getLast().end){ // 当前区间与最后一个加入的区间有重叠 if(list.get(i).end <= linkedlist.getLast().end){ // 当前区间已经被前面的区间囊括 continue; } // 合并区间 list.get(i).start = linkedlist.getLast().start; linkedlist.removeLast(); linkedlist.add(list.get(i)); }else{ linkedlist.add(list.get(i)); } } Interval[] res = new Interval[linkedlist.size()]; Iterator<Interval> iterator = linkedlist.iterator(); int index = 0; while(iterator.hasNext()){ res[index++] = iterator.next(); } return res; } }
/** * struct Interval { * int start; * int end; * Interval(int s, int e) : start(start), end(e) {} * }; */ #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param Intervals Interval类vector * @param newInterval Interval类 * @return Interval类vector */ vector<Interval> insertInterval(vector<Interval>& Intervals, Interval newInterval) { vector<Interval>ans; if(Intervals.empty()){ ans.push_back(newInterval); return ans; } Intervals.push_back(newInterval); sort(Intervals.begin(),Intervals.end(),[](Interval a,Interval b){return a.start<b.start;}); for(int i=0;i<Intervals.size()-1;i++){ Interval temp=Intervals[i]; while(temp.end>=Intervals[i+1].start){ temp.end=max(temp.end,Intervals[i+1].end); i++; } ans.push_back(temp); } if(ans.back().end>=Intervals.back().end){ return ans; }else{ ans.push_back(Intervals.back()); return ans; } } };
class Solution: def insertInterval(self , Intervals: List[Interval], newInterval: Interval) -> List[Interval]: # write code here if len(Intervals) == 0: return [newInterval] res = [] res.append(Intervals[0]) selected = False for i in range(len(Intervals)): if not selected: if self.is_interval_intersect(newInterval, res[-1]): res[-1].start = min(res[-1].start, newInterval.start) res[-1].end = max(res[-1].end, newInterval.end) selected = True if self.is_interval_intersect(res[-1], Intervals[i]): res[-1].start = min(res[-1].start, Intervals[i].start) res[-1].end = max(res[-1].end, Intervals[i].end) else: res.append(Intervals[i]) if not selected: res.append(newInterval) return res def is_interval_intersect(self, i1, i2): a1,b1 = i1.start,i1.end a2,b2 = i2.start,i2.end if a1 <= a2 <= b1&nbs***bsp;a1 <= b2 <= b1&nbs***bsp;a2 <= a1 <= b2: return True else: return False
import java.util.*; /* * public class Interval { * int start; * int end; * public Interval(int start, int end) { * this.start = start; * this.end = end; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param Intervals Interval类一维数组 * @param newInterval Interval类 * @return Interval类一维数组 */ public Interval[] insertInterval (Interval[] Intervals, Interval newInterval) { // write code here Arrays.sort(Intervals, (i1, i2) -> { if(i1.start == i2.start) { return i1.end - i2.end; } return i1.start - i2.start; }); int start = newInterval.start; int end = newInterval.end; List<Interval> list = new ArrayList<>(); int i = 0; for(; i < Intervals.length; i++) { Interval in = Intervals[i]; // 不能合并 if(start > in.end || end < in.start) { list.add(new Interval(in.start, in.end)); continue; }else { start = Math.min(start, in.start); end = Math.max(end, in.end); } } list.add(new Interval(start, end)); Interval[] res = new Interval[list.size()]; for(int j = 0; j < res.length; j++) { res[j] = list.get(j); } Arrays.sort(res, (i1, i2) -> { if(i1.start == i2.start) { return i1.end - i2.end; } return i1.start - i2.start; }); return res; } }
class Solution { public Interval[] insertInterval (Interval[] intervals, Interval newInterval){ ArrayList<Interval> list = new ArrayList<>(); for (Interval interval : intervals) { if (newInterval.end < interval.start || newInterval.start > interval.end){ list.add(interval); }else { newInterval.start = Math.min(newInterval.start, interval.start); newInterval.end = Math.max(newInterval.end, interval.end); } } list.add(newInterval); Interval[] array = list.toArray(new Interval[0]); Arrays.sort(array, (o1, o2) -> o1.start - o2.start); return array; } }Java解法 不相交区间正在加在返回结果中 相交的区间取[min(L1, L2), max(R1, R2)]即可
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param Intervals Interval类vector * @param newInterval Interval类 * @return Interval类vector */ vector<Interval> insertInterval(vector<Interval>& Intervals, Interval newInterval) { // write code here int i = 0; int n = Intervals.size(); int s = newInterval.start , e = newInterval.end; vector<Interval> res; while(i < n && Intervals[i].end < s){ res.push_back(Intervals[i]); i++; } res.push_back(newInterval); while(i < n && res.back().end >= Intervals[i].start){ res.back().start = min(Intervals[i].start,res.back().start); res.back().end = max(Intervals[i].end,res.back().end); i++; } while(i < n) {res.push_back(Intervals[i]);i++;} return res; } };
import java.util.*; /* * public class Interval { * int start; * int end; * public Interval(int start, int end) { * this.start = start; * this.end = end; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param Intervals Interval类一维数组 * @param newInterval Interval类 * @return Interval类一维数组 */ public Interval[] insertInterval (Interval[] Intervals, Interval newInterval) { // write code here if(Intervals.length == 0){ return new Interval[]{newInterval}; } ArrayList<Interval> list = new ArrayList<>(); list.add(newInterval); for(int i = 0; i < Intervals.length; i++){ list.add(Intervals[i]); } // 先对所有区间按起点升序终点也升序进行二次排序,这样可以保证相同起点的区间,更大的区间在后面 Collections.sort(list, (a, b) -> a.start != b.start? a.start - b.start: a.end - b.end); // 用双端链表构建一个结果集 LinkedList<Interval> linkedlist = new LinkedList<>(); linkedlist.add(list.get(0)); for(int i = 1; i < list.size(); i++){ if(list.get(i).start <= linkedlist.getLast().end){ // 当前区间与最后一个加入的区间有重叠 if(list.get(i).end <= linkedlist.getLast().end){ // 当前区间已经被前面的区间囊括 continue; } // 合并区间 list.get(i).start = linkedlist.getLast().start; linkedlist.removeLast(); linkedlist.add(list.get(i)); }else{ linkedlist.add(list.get(i)); } } Interval[] res = new Interval[linkedlist.size()]; Iterator<Interval> iterator = linkedlist.iterator(); int index = 0; while(iterator.hasNext()){ res[index++] = iterator.next(); } return res; } }