57. Insert Interval 发表于 2022-05-20 Linked List123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384class Solution { private static class Entry { private int[] interval; private Entry prev; private Entry next; public Entry(int[] interval, Entry prev) { this.interval = interval; this.prev = prev; } } public int[][] insert(int[][] intervals, int[] newInterval) { // 首先判断是否与已有区间重叠,如果不重叠,则插入至指定位置,如果重叠则需要合并区间 Entry dummyHead = new Entry(null, null); Entry current = dummyHead; Entry insertEntry = dummyHead; Entry targetEntry = null; for (int[] interval : intervals) { current.next = new Entry(interval, current); current = current.next; if (interval[0] < newInterval[0]) { insertEntry = current; } if (targetEntry == null && hasCommonInterval(interval, newInterval)) { targetEntry = current; } } if (targetEntry == null) { // 无重复区间,将区间插入即可 Entry next = insertEntry.next; insertEntry.next = new Entry(newInterval, insertEntry); insertEntry.next.next = next; if (next != null) { next.prev = insertEntry.next; } } else { // 存在重复区间,插入并合并区间 targetEntry.interval = mergeInterval(targetEntry.interval, newInterval); // 合并区间后,当前区间左侧和右侧可能与左右区间存在交集,则需要尝试不停向左侧或右侧合并 while (targetEntry.prev != null && targetEntry.prev.interval != null && hasCommonInterval(targetEntry.prev.interval, targetEntry.interval)) { targetEntry.interval = mergeInterval(targetEntry.prev.interval, targetEntry.interval); Entry prevOfPrev = targetEntry.prev.prev; if (prevOfPrev != null) { prevOfPrev.next = targetEntry; } targetEntry.prev = prevOfPrev; } while (targetEntry.next != null && targetEntry.next.interval != null && hasCommonInterval(targetEntry.next.interval, targetEntry.interval)) { targetEntry.interval = mergeInterval(targetEntry.next.interval, targetEntry.interval); Entry nextOfNext = targetEntry.next.next; if (nextOfNext != null) { nextOfNext.prev = targetEntry; } targetEntry.next = nextOfNext; } } List<int[]> intervalList = new LinkedList<>(); current = dummyHead.next; while (current != null) { intervalList.add(current.interval); current = current.next; } return intervalList.toArray(new int[0][]); } private int[] mergeInterval(int[] a, int[] b) { return new int[]{Math.min(a[0], b[0]), Math.max(a[1], b[1])}; } private boolean hasCommonInterval(int[] a, int[] b) { if (a[0] > b[0]) { return hasCommonInterval(b, a); } return a[1] >= b[0]; }} Iterate123456789101112131415161718192021222324252627282930313233343536class Solution { public int[][] insert(int[][] intervals, int[] newInterval) { boolean inserted = false; int start = newInterval[0], end = newInterval[1]; List<int[]> list = new ArrayList<>(intervals.length + 1); for (int[] interval : intervals) { if (interval[1] < newInterval[0]) { // 当前区间位于新区间左侧 list.add(interval); } else if (interval[0] > newInterval[1]) { // 当前区间位于新区间右侧 if (!inserted) { // 遇到了新的不交集的区间,如果之前存在交集的区间,则在此处添加 list.add(new int[]{start, end}); inserted = true; } list.add(interval); } else { // 存在交集 start = Math.min(start, interval[0]); end = Math.max(end, interval[1]); } } // 处理交集区间全部位于数组尾部的情况 if (!inserted) { list.add(new int[]{start, end}); } int[][] array = new int[list.size()][]; for (int i = 0; i < list.size(); i++) { array[i] = list.get(i); } return array; }} Reference57. Insert Interval