57. Insert Interval - Medium

前往題目

這題之前做過，所以照搬一下

想法

• 這題卡在不知道如何處理interval重疊的問題
• 但其實很簡單，因為有重疊的部分只要取左值最小與右值最大就可以了，用以下兩個語句

newInterval[0] = Math.min(currInterval[0], newInterval[0]); // Merge the interval
newInterval[1] = Math.max(currInterval[1], newInterval[1]);

• 這題大家都是用新的arraylist來儲存，因為好像沒辦法預測array需要多大的空間

思路

1. 開新的arraylist
2. 我們需要看過所有的array，因此遍歷所有intervals
3. 關鍵是如何處理merge的問題
4. 分成三個條件
   1. 當newInterval小於currentInterval（因為sorted所以只要看currentInterval左邊那位是否小於newInterval右邊那位）
   2. 當newInterval大於currentInterval，直接加currentInterval到result array就好了
   3. 剩下的就只有相交的可能，Merge很簡單，但記得不要return，因為不知道有沒有和之後的interval相交
5. Return前記得把最後的interval加上去

Code

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();

        // Check and iterate all the intervals
        for(int[] currInterval: intervals){
          // When newInterval is smaller than current interval
          if(newInterval[1] < currInterval[0]){
            result.add(newInterval); // Add to the result array
            newInterval = currInterval; // currInterval to be the next to insert
          } else if(currInterval[1] < newInterval[0]){// When newInterval is larger
            result.add(currInterval);
          } else{ // Intervals are overlapping
            newInterval[0] = Math.min(currInterval[0], newInterval[0]); // Merge the interval
            newInterval[1] = Math.max(currInterval[1], newInterval[1]);
          }

        }

        // Insert the last interval
        result.add(newInterval);

        return result.toArray(new int[result.size()][]);
    }
}