Bài 57 Leetcode: Insert Interval

Đề bài:

Bạn được cho một mảng các khoảng thời gian không chồng chéo, trong đó intervals[i] = [start_i, end_i] đại diện cho điểm bắt đầu và kết thúc của khoảng thời gian i^th và intervals đã được sắp xếp theo thứ tự tăng dần của start_i. Bạn cũng được cho một khoảng thời gian newInterval = [start, end] đại diện cho điểm bắt đầu và kết thúc của một khoảng thời gian khác.

Chèn newInterval vào mảng intervals sao cho intervals vẫn được sắp xếp theo thứ tự tăng dần của start_i và intervals vẫn không có bất kỳ khoảng thời gian nào chồng chéo (hợp nhất các khoảng thời gian chồng chéo nếu cần).

Trả về intervals sau khi đã chèn.

Ví dụ 1:

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

Ví dụ 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Giải thích: Vì khoảng thời gian mới [4,8] chồng chéo với [3,5], [6,7], [8,10].

Ràng buộc:

• 0 <= độ dài của mảng intervals <= 10⁴
• intervals[i] có độ dài bằng 2
• 0 <= start_i <= end_i <= 10⁵
• intervals được sắp xếp theo start_i theo thứ tự tăng dần.
• newInterval có độ dài bằng 2
• 0 <= start <= end <= 10⁵

Giải thích thuật toán bằng C ++

class Solution {
 public:
  vector<vector<int>> insert(vector<vector<int>>& intervals,
                             vector<int>& newInterval) {
    const int n = intervals.size();
    vector<vector<int>> ans;
    int i = 0;

    while (i < n && intervals[i][1] < newInterval[0])
      ans.push_back(intervals[i++]);

    // Merge overlapping intervals
    while (i < n && intervals[i][0] <= newInterval[1]) {
      newInterval[0] = min(newInterval[0], intervals[i][0]);
      newInterval[1] = max(newInterval[1], intervals[i][1]);
      ++i;
    }

    ans.push_back(newInterval);

    while (i < n)
      ans.push_back(intervals[i++]);

    return ans;
  }
};

Đây là một đoạn mã C++ để chèn một khoảng thời gian mới vào một mảng các khoảng thời gian đã được sắp xếp và trả về một mảng mới sau khi chèn.

Hàm `insert` nhận đầu vào là một vector 2D `intervals` chứa các khoảng thời gian đã được sắp xếp và một vector `newInterval` đại diện cho khoảng thời gian mới cần chèn. Nó trả về một vector 2D `ans` chứa các khoảng thời gian sau khi đã chèn.

Đầu tiên, biến `n` được gán giá trị là độ dài của `intervals`.

Sau đó, một vector 2D `ans` rỗng được khởi tạo để lưu trữ các khoảng thời gian sau khi chèn. Biến `i` được khởi tạo với giá trị 0 để đánh dấu vị trí hiện tại trong mảng `intervals`.

Trong vòng lặp while đầu tiên, các khoảng thời gian trong `intervals` mà kết thúc trước khoảng thời gian mới (`intervals[i][1] < newInterval[0]`) được thêm vào `ans` mà không cần thay đổi.

Sau đó, trong vòng lặp while thứ hai, các khoảng thời gian trong `intervals` mà có khả năng chồng chéo với khoảng thời gian mới (`intervals[i][0] <= newInterval[1]`) được hợp nhất với khoảng thời gian mới. Khoảng thời gian mới được cập nhật để bao gồm cả khoảng thời gian trong `intervals[i]` bằng cách chọn giá trị nhỏ nhất cho `newInterval[0]` và giá trị lớn nhất cho `newInterval[1]`. Sau đó, biến `i` được tăng lên để xử lý khoảng thời gian tiếp theo.

Khi vòng lặp kết thúc, khoảng thời gian mới đã được hợp nhất với các khoảng thời gian trong `intervals`, và nó được thêm vào `ans`.

Cuối cùng, các khoảng thời gian còn lại trong `intervals` sau vị trí `i` cũng được thêm vào `ans`.

Hàm trả về vector `ans` chứa các khoảng thời gian sau khi đã chèn khoảng thời gian mới.

Đây là một cách tiếp cận để chèn và hợp nhất các khoảng thời gian trong một mảng đã sắp xếp.

Giải thích thuật toán bằng Java

class Solution {
  public int[][] insert(int[][] intervals, int[] newInterval) {
    final int n = intervals.length;
    List<int[]> ans = new ArrayList<>();
    int i = 0;

    while (i < n && intervals[i][1] < newInterval[0])
      ans.add(intervals[i++]);

    // Merge overlapping intervals.
    while (i < n && intervals[i][0] <= newInterval[1]) {
      newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
      newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
      ++i;
    }

    ans.add(newInterval);

    while (i < n)
      ans.add(intervals[i++]);

    return ans.toArray(int[][] ::new);
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    n = len(intervals)
    ans = []
    i = 0

    while i < n and intervals[i][1] < newInterval[0]:
      ans.append(intervals[i])
      i += 1

    # Merge overlapping intervals.
    while i < n and intervals[i][0] <= newInterval[1]:
      newInterval[0] = min(newInterval[0], intervals[i][0])
      newInterval[1] = max(newInterval[1], intervals[i][1])
      i += 1

    ans.append(newInterval)

    while i < n:
      ans.append(intervals[i])
      i += 1

    return ans