57. Insert Interval.md

57. Insert Interval

---

leetcode Daily Challenge on September 13th, 2020.

leetcode-cn Daily Challenge on November 4th, 2020.

---

Difficulty : Medium

Related Topics : Array、Sort

---

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Example 3:

Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]

Example 4:

Input: intervals = [[1,5]], newInterval = [2,3]
Output: [[1,5]]

Example 5:

Input: intervals = [[1,5]], newInterval = [2,7]
Output: [[1,7]]

Constraints:

• 0 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= intervals[i][0] <= intervals[i][1] <= 10^5
• intervals is sorted by intervals[i][0] in ascending order.
• newInterval.length == 2
• 0 <= newInterval[0] <= newInterval[1] <= 10^5

---

Solution

• mine
  • Java
    • Runtime: 5 ms, faster than 11.26%, Memory Usage: 45.1 MB, less than 9.15% of Java online submissions

      // O(M) time
      // O(M) space
      // M = max(intervals[i][1], newInterval[1], intervals.length)
      public int[][] insert(int[][] intervals, int[] newInterval) {
          int max = 0;
          for(int[] in : intervals){
              max = Math.max(max, in[1]);
          }
          max = Math.max(max, newInterval[1]);
      
          Map<Integer, int[]> map = new HashMap<>();
          int[] record = new int[max + 1];
          for(int[] in : intervals){
              record[in[0]]++;
              record[in[1]]--;
              if(in[0] == in[1]) map.put(in[0], in);
          }
          record[newInterval[0]]++;
          record[newInterval[1]]--;
          if(newInterval[0] == newInterval[1]) map.put(newInterval[0], newInterval);
      
          int t = 0;
          int s = -1;
          LinkedList<int[]> list = new LinkedList<>();
          for(int i = 0; i <= max; i++){
              t += record[i];
      
              if(t > 0 && s == -1){
                  s = i;
              } else if(t == 0){
                  if(s != -1){
                      list.add(new int[]{s, i});
                      s = -1;
                  }else if(map.containsKey(i)){
                      list.add(map.get(i));
                  }
              }
      
          }
          int[][] res = new int[list.size()][];
          int i = 0;
          while(!list.isEmpty()) res[i++] = list.removeFirst();
      
          return res;
      }
      

---

• the most votes

• Runtime: 1 ms, faster than 96.82%, Memory Usage: 45.2 MB, less than 8.75% of Java online submissions

  //O(N)time
  //O(1)space
  public int[][] insert(int[][] intervals, int[] newInterval) {
     // corner case
      if (newInterval == null) {
          return intervals;
      } else if (intervals == null || intervals.length == 0) {
          return new int[][] {newInterval};
      }
      int s = newInterval[0];
      int e = newInterval[1];
      int con = 0;
      for (int i = 0; i < intervals.length; i ++) { // first to find where to set the start
          int curStart = intervals[i][0];
          int curEnd = intervals[i][1];
          if (s <= curStart) {  // if    prevEnd < s <= curStart, s = s
              con = i;
              break;
          } else if (s <= curEnd) { // if  curStart < s <= curEnd, s = curStart
              s = curStart;
              con = i;
              break;
          }
          con ++;
      }
      // [continue, end) is the range to delete the chunk
      int end = con;
      for (int i = con; i < intervals.length; i ++) { // find where to set the end
          int curStart = intervals[i][0];
          int curEnd = intervals[i][1];
          if (e < curStart) {
              break;
          } else if (e <= curEnd) {
              e = curEnd;
              end ++;
              break;
          }
          end ++;
      }
      ArrayList<int[]> res = new ArrayList<>();
      for (int i = 0; i < intervals.length; i ++) {
          if (i == con) {
              res.add(new int[]{s, e});
          }
          if (i >= con && i < end) {
              continue;
          } else {
              res.add(intervals[i]);
          }
      }
      if (con >= intervals.length) {
          res.add(newInterval);
      }
      int[][] a = new int[res.size()][];
      for (int i = 0; i < a.length; i ++) {
          a[i] = res.get(i);
      }
      return a;
  }
  

---