算法面試套路｜合併區間（Merge Intervals）

本篇內容主要為 Grokking the Coding Interview: Patterns for Coding Questions 的翻譯與整理，行有餘力建議可以購買該專欄課程閱讀並在上面進行練習。

重點整理

• 合併區間（Merge Intervals）
• 策略：給定兩個區間，彼此之間共有六種不同的交互模式
• 題型：
  • 涉及間隔（intervals）的問題
  • 找尋重疊部分、合併重疊間隔

題目匯總

• 0056 Merge Intervals
• 0057 Insert Interval
• 0252 Meeting Rooms
• 0253 Meeting Rooms II
• 0435 Non-overlapping Intervals
• 0729 My Calendar I
• 0759 Employee Free Time
• 0986 Interval List Intersections
• 1094 Car Pooling
• 1288 Remove Covered Intervals

[例題] Merge Intervals

問題

給定一個區間陣列，合併所有重疊的區間，並返回這些區間所組成的陣列。比如 [[1,4], [2,5], [7,9]] 合併後會得到 [[1,5], [7,9]]：

Exapmles

Intervals: [[6,7], [2,4], [5,9]]
Output: [[2,4], [5,9]], Since the intervals [6,7] and [5,9] overlap, we merged them into one [5,9].

Intervals: [[1,4], [2,6], [3,5]]
Output: [[1,6]], Since all the given intervals overlap, we merged them into one.

題解

考慮兩個區間 a 和 b 滿足 a.start <= b.start，一共會有四種交互情況：

狀況	圖示
彼此不重疊 部分的 b 與 a 重疊 所有的 b 在 a 裡面 所有的 a 在 b 裡面，且起點相同

我們的目標是要合併重複區間，依據上述 (2), (3), (4) 的重疊情況，合併的方式如下：

c.start = a.start            // 左側固定
c.end = max(a.end, b.end)    // 右側取大

因此我們的演算法策略為：

1. 先將所有的區間進行排序，確保 a.start <= b.start
2. 如果發生「重疊」（即 b.start <= a.end）的狀況，需要合併為新的區間 c
3. 反覆上述動作，如果下一個區間與得到的區間 c 有重疊的狀況

代碼

C++

class MergeIntervals {
 public:
  static vector<Interval> mergeIntervals(vector<Interval> &intervals) {
    if (intervals.size() < 2) {
      return intervals;
    }
    
    sort(intervals.begin(), intervals.end(),
         [](const Interval &x, const Interval &y) { return x.start < y.start; });
    
    vector<Interval> mergedIntervals;
    vector<Interval>::const_iterator intervalItr = intervals.begin();
    Interval interval = *intervalItr++;
    int start = interval.start;
    int end = interval.end;
    
    while (intervalItr != intervals.end()) {
      interval = *intervalItr++;
      if (interval.start <= end) {
        end = max(interval.end, end);  
      } else {
        mergedIntervals.push_back({ start, end });
        start = interval.start;
        end = interval.end;
      }
    }
    
    mergedIntervals.push_back({ start, end });
    return mergedIntervals;
  }
}

Java

class MergeIntervals {
  public static List<Interval> merge(List<Interval> intervals) {
    if (intervals.size() < 2) {
      return intervals;
    }
    
    // sort the intervals by start index
    Collections.sort(intervals, (a, b) -> Integer.compare(a.start, b.start));
    
    List<Interval> mergedIntervals = new LinkedList<Interval>();
    Iterator<Interval> intervalItr = intervals.iterator();
    Interval interval = intervalItr.next();
    
    int start = interval.start;
    int end = interval.end;
    
    while (intervalItr.hasNext()) {
      interval = intervalItr.next();
      
      if (interval.start <= end) {    // overlapping intervals, adjust the end
        end = Math.max(interval.end, end);
      } else {                        // non-overlapping interval, add the previous interval and reset
        mergedIntervals.add(new Interval(start, end));
        start = interval.start;
        end = interval.end;
      }
    }
    
    // add the last interval
    mergedIntervals.add(new Interval(start, end));
    
    return mergedIntervals;
    
  }
}

JavaScript

const mergeIntervals = (intervals) => {
  if (intervals.length < 2) {
    return intervals;
  }
  
  intervals.sort((a, b) => a.start - b.start);
  
  const mergedIntervals = [];
  let start = intervals[0].start;
  let end = intervals[0].end;
  
  for (let i = 1; i < intervals.length; ++i) {
    const interval = intervals[i];
    
    if (interval.start <= end) {
      end = Math.max(interval.end, end);
    } else {
      mergedIntervals.push(new Interval(start, end));
      start = interval.start;
      end = interval.end;
    }
  }
  
  mergedIntervals.push(new Interval(start, end));
  return mergedIntervals;
}

Python

def merge_intervals(intervals):
    if len(intervals) < 2:
        return intervals

    intervals.sort(key=lambda x: x.start)

    mergedIntervals = []
    start = intervals[0].start
    end = intervals[0].end

    for i in range(1, len(intervals)):
        interval = intervals[i]
        if interval.start <= end:
            end = max(interval.end, end)
        else:
            mergedIntervals.append(Interval(start, end))
            start = interval.start
            end = interval.end

    mergedIntervals.append(Interval(start, end))

    return mergedIntervals

分析

• 時間複雜度：
  $\mathcal{O}(n\log n)$，其中遍歷需
  $\mathcal{O}(n)$ 而排序需
  $\mathcal{O}(n\log n)$，又
  $\mathcal{O}(n\log n)>\mathcal{O}(n)$
• 空間複雜度：
  $\mathcal{O}(n)$，需要
  $\mathcal{O}(n)$ 進行排序且需要
  $\mathcal{O}(n)$ 用來儲存返回的區間陣列

[例題] Insert Interval

問題

給定一個由不重疊區間所組成的陣列，並且該陣列已經根據起始位置進行排序，將一個額外給定的區間插入正確的位置，並合併重疊區間使返回的區間陣列中為彼此獨立的區間。

Examples

Input: Intervals=[[1,3], [5,7], [8,12]], New Interval=[4,6]
Output: [[1,3], [4,7], [8,12]], After insertion, since [4,6] overlaps with [5,7], we merged them into one [4,7].

Input: Intervals=[[1,3], [5,7], [8,12]], New Interval=[4,10]
Output: [[1,3], [4,12]], After insertion, since [4,10] overlaps with [5,7] & [8,12], we merged them into [4,12].

Input: Intervals=[[2,3],[5,7]], New Interval=[1,4]
Output: [[1,4], [5,7]], After insertion, since [1,4] overlaps with [2,3], we merged them into one [1,4].

題解

倘若給定陣列並未排序，我們可以簡單地將新的區間添加至陣列中，並呼叫 Merge Intervals 中的 merge() 函數來處理。但既然題目已經說給定的陣列 有序，我們需要想看看是否能夠有比

$\mathcal{O}(n\log n)$ 更好的解決方法。

當我們要在一個已經排序的區間陣列中插入一個新的區間時，首先需要找到可以放置新區間的正確位置；換句話說，我們需要跳過在新區間開始前之前結束的所有區間，亦即遍歷區間陣列，並使用以下條件跳過這些不滿足條件的區間：

intervals[i].end < newInterval.start

找到正確的位置後，可以遵循類似於 Merge Intervals 的做法來插入或合併新的區間。在不失一般性的情況下將新區間稱為 a，而滿足上述條件的第一個區間稱為 b，則共有以下五種可能性：

狀況	圖示
彼此不重疊，直接插入 a 部分的 b 與 a 重疊，合併為 c(a.start, b.end) 所有的 b 在 a 裡面，合併為 c(a.start, a.end) 部分的 a 與 b 重疊，合併為 c(b.start, a.end) 所有的 a 在 b 裡面，合併為 c(b.start, b.end)

要處理上述 (2), (3), (4) 和 (5) 的重疊狀況，只需要執行以下操作：

c.start = min(a.start, b.start)  // 左側取小
c.end = max(a.end, b.end)        // 右側取大

因此我們的演算法策略為：

1. 遍歷陣列跳過滿足 intervals[i].end < newInterval.start 的區間
2. 找到不滿足條件的區間，判斷左右邊界並合併得到新區間 c
3. 反覆上述動作，如果下一個區間與得到的區間 c 有重疊的狀況

代碼

C++

class InsertInterval {
 public:
  static vector<Interval> insert(const vector<Interval> &intervals, Interval newInterval) {
    if (intervals.empty()) {
      return vector<Interval> { newInterval };
    }
    
    vector<Interval> mergedIntervals;
    int idx = 0;
    
    while (idx < intervals.size() && intervals[idx].end < newInterval.start) {
      mergedIntervals.push_back(intervals[idx]);
      idx++;
    }
    
    while (idx < intervals.size() && intervals[idx].start <= newInterval.end) {
      newInterval.start = min(intervals[idx].start, newInterval.start);
      newInterval.end = max(intervals[idx].end, newInterval.end);
      idx++;
    }
    
    mergedIntervals.push_back(newInterval);
    
    while (idx < intervals.size()) {
      mergedIntervals.push_back(intervals[idx]);
      idx++;
    }
    
    return mergedIntervals;
  }
}

Java

class InsertInterval {
  public static List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    if (intervals == null || intervals.isEmpty()) {
      return Arrays.asList(newInterval);
    }
    
    List<Interval> mergedIntervals = new ArrayList<>();
    
    int i = 0;
    // skip (and add to output) all intervals that come before the newInterval
    while (i < intervals.size() && intervals.get(i).end < newInterval.start) {
      mergedIntervals.add(intervals.get(i++));
    }
    
    // merge all intervals that overlap with newInterval
    while (i < intervals.size() && intervals.get(i).start <= newInterval.end) {
      newInterval.start = Math.min(intervals.get(i).start, newInterval.start);
      newInterval.end = Math.max(intervals.get(i).end, newInterval.end);
      i++;
    }
    
    // insert the newInterval
    mergedIntervals.add(newInterval);
    
    // add all the remaining intervals to the output
    while (i < intervals.size()) {
      mergedIntervals.add(intervals.get(i++));
    }
    
    return mergedIntervals;
  }
}

JavaScript

const insertInterval = (intervals, newInterval) {
  let idx = 0;
  let merged = [];
  
  while (idx < intervals.length && intervals[idx].end < newInterval.start) {
    merged.push(intervals[idx]);
    idx += 1;
  }
  
  while (idx < intervals.length && intervals[idx].start <= newInterval.end) {
    newInterval.start = Math.min(intervals[idx].start, newInterval.start);
    newInterval.end = Math.max(intervals[idx].end, newInterval.end);
    idx += 1;
  }
  
  merged.push(newInterval);
  
  while (idx < intervals.length) {
    merged.push(intervals[idx]);
    i += 1;
  }
  
  return merged;
}

Python

def insert_interval(intervals, new_interval):
    merged = []
    i = 0
    start = 0
    end = 1
    
    while i < len(intervals) and intervals[i][end] < new_interval[start]:
        merged.append(intervals[i])
        i += 1
        
    while i < len(intervals) and intervals[i][start] <= new_interval[end]:
        new_interval[start] = min(intervals[i][start], new_interval[start])
        new_interval[end] = max(intervals[i][end], new_interval[end])
        i += 1
        
    merged.append(new_interval)
    
    while i < len(intervals):
        merged.append(intervals[i])
        i += 1
        
    return merged

分析

• 時間複雜度：
  $\mathcal{O}(n)$
• 空間複雜度：
  $\mathcal{O}(n)$

[例題] Intervals Intersection

問題

給定兩個區間陣列，找出兩個陣列的交集部分，每一個陣列中的區間彼此獨立且已經依據起始位置進行排序。

Examples:

Input: arr1=[[1, 3], [5, 6], [7, 9]], arr2=[[2, 3], [5, 7]]
Output: [2, 3], [5, 6], [7, 7].

Input: arr1=[[1, 3], [5, 7], [9, 12]], arr2=[[5, 10]]
Output: [5, 7], [9, 10].

題解

這個問題可以採用 合併區間（Merge Intervals） 模式求解，正如我們在 Insert Interval 中所討論的，在兩個間隔 a 和 b 之間有五種交互的狀況；仔細觀察不難發現，每當兩個區間重疊時，其中一個區間的開始位置會位於另外一個區間中，這個事實可以幫助我們確認兩個區間是否重疊。

此時，兩個重疊區間交集的部分，可以透過以下方式判斷其區間：

start = max(a.start, b.start)  // 左側取大
end = min(a.end, b.end)        // 右側取小

因此我們只需要遍歷兩個陣列，同時查看是否有區間重疊，重疊的部分計算其交集並插入結果陣列中，直到結束。

代碼

C++

class Intersection {
 public:
  static vector<Interval> merge(const vector<Interval> &arr1, const vector<Interval> &arr2) {
    vector<Interval> result;
    int i = 0;
    int j = 0;
    
    while (i < arr1.size() && j < arr2.size()) {
      if ((arr1[i].start >= arr2[j].start) && arr1[i].start <= arr2[j].end) ||
          (arr2[j].start >= arr1[i].start) && arr2[j].start <= arr1[i].end)) {
        result.push_back({max(arr1[i].start, arr2[j].start), min(arr1[i].end, arr2[j].end)});
      }
      
      if (arr1[i].end < arr2[j].end) {
        i++;
      } else {
        j++;
      }
    }
    
    return result;
  }
};

Java

class IntervalsIntersection {
  public static Interval[] merge(Interval[] arr1, Interval[] arr2) {
    List<Interval> result = new ArrayList<Interval>();
    
    int i = 0;
    int j = 0;
    while (i < arr1.length && j < arr2.length) {
      if ((arr1[i].start >= arr2[j].start && arr1[i].start <= arr2[j].end)
          || (arr2[j].start >= arr1[i].start && arr2[j].start <= arr1.[i].end)) {
        result.add(new Interval(Math.max(arr1[i].start, arr2[j].start), Max.min(arr1[i].end, arr2[j].end)));
      }
    }
    
    if (arr1[i].end < arr2[j].end) {
      i++;
    } else {
      j++;
    }
    
    return result.toArray(new Interval[result.size()]);
  }
}

JavaScript

const IntersectionIntervals = (intervals_a, intervals_b) => {
  let results = [];
  let i = 0;
  let j = 0;
  
  while (i < intervals_a.length && j < intervals_b.length) {
    if ((intervals_a[i].start >= intervals_b[j].start && intervals_a[i].start <= intervals_b[j].end) ||
        (intervals_b[j].start >= intervals_a[i].start && intervals_b[j].start <= intervals_a[i].end)) {
      const left = Math.max(intervals_a[i].start, intervals_b[j].start);
      const right = Math.min(intervals_a[i].end, intervals_b[j].end);
      
      result.push(newInterval(left, right));
    }
    
    if (intervals_a[i].end < intervals_b[j].end) {
      i += 1;
    } else {
      j += 1;
    }
  }
  
  return result;
}

Python

def intersection(intervals_a, intervals_b):
    result = []
    i, j, start, end = 0, 0, 0, 1
    
    while i < len(intervals_a) and j < len(intervals_b):
        a_overlaps_b = intervals_a[i][start] >= intervals_b[j][start] and intervals_a[i][start] <= intervals_b[j][end]
        b_overlaps_a = intervals_b[j][start] >= intervals_a[i][start] and intervals_b[j][start] <= intervals_a[i][end]
        
        if (a_overlaps_b or b_overlaps_a):
            result.append([max(intervals_a[i][start], intervals_b[j][start]), min(intervals_a[i][end], intervals_b[j][end])])
            
        if intervals_a[i][end] < intervals_b[j][end]:
            i += 1
        else:
            j += 1
    
    return result

分析

• 時間複雜度：
  $\mathcal{O}(n+m)$
• 空間複雜度：
  $\mathcal{O}(n+m)$，若不計返回陣列所需的空間則為
  $\mathcal{O}(1)$

[例題] Conflicting Appointments

給定一組陣列，其中有

$N$ 個約會行程（以區間表示時間範圍），撰寫一支程式判斷一個人是否可以出席所有的約會行程。

問題

Examples

Input: [[1,4], [2,5], [7,9]]
Output: false. Since [1,4] and [2,5] overlap, a person cannot attend both of these appointments.

Input: [[6,7], [2,4], [8,12]]
Output: true. None of the appointments overlap, therefore a person can attend all of them.

Input: [[4,5], [2,3], [3,6]]
Output: false. Since [4,5] and [3,6] overlap, a person cannot attend both of these appointments.

題解

這個問題可以採用 合併區間（Merge Intervals） 模式求解，我們需要做的是先將約會行程依據起始時間進行排序，再逐個確認這些區間是否存在重疊的狀況。

1. 注意判斷的邊界需不需要包含
2. 存在重疊的條件

代碼

C++

class ConflictingAppointments {
 public:
  static bool canAttendAllAppointments(vector<Interval>& intervals) {
    sort(intervals.begin(), intervals.end(), [](const Interval& x, const Interval& y) { return x.start < y.start; });
    
    for (int i = 1; i < intervals.size(); i++) {
      if (intervals[i].start < intervals[i - 1].end) {
        return false;
      }
    }
    
    return true;
  }
}

Java

class ConflictingAppointments {
  public static boolean canAttendAllAppointments(Interval[] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a.start, b.start));
    
    for (int i = 1; i < intervals.length; i++) {
      if (intervals[i].start < intervals[i - 1].end) {
        return false;
      }
    }
    
    return true;
  }
}

JavaScript

const canAttendAllAppointments = (intervals) => {
  intervals.sort((a, b) => a.start - b.start);
  
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i].start < intervals[i - 1].end) {
      return false;
    }
  }
  
  return true;
}

Python

def can_attend_all_appointments(intervals):
    intervals.sort(key=lambda x: x[0])
    start, end = 0, 1
    
    for i in range(1, len(intervals)):
        if intervals[i][start] < intervals[i-1][end]:
            return False
    
    return True

分析

• 時間複雜度：
  $\mathcal{O}(n\log n)$
• 空間複雜度：
  $\mathcal{O}(n)$ 排序所需空間

參考資料

• Merge Overlapping Intervals | GeeksforGeeks
• Coding Patterns: Merge Intervals | emre.me

Published on HackMD

https://hackmd.io/@Hsins

作者

H.-H. Peng (Hsins)

授權許可

CC BY-NC-SA 4.0