Bài 56 Leetcode: Merge Intervals

Đề bài:

Cho một mảng các khoảng thời gian, trong đó intervals[i] = [start_i, end_i], hợp nhất tất cả các khoảng thời gian chồng chéo và trả về một mảng chứa các khoảng thời gian không chồng chéo mà bao gồm tất cả các khoảng thời gian trong đầu vào.

Ví dụ 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Giải thích: Vì khoảng thời gian [1,3] và [2,6] chồng chéo nhau, nên hợp nhất chúng thành [1,6].

Ví dụ 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Giải thích: Khoảng thời gian [1,4] và [4,5] được xem là chồng chéo nhau.

Ràng buộc:

• 1 <= độ dài của mảng intervals <= 10⁴
• intervals[i] có độ dài bằng 2
• 0 <= start_i <= end_i <= 10⁴

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

class Solution {
 public:
  vector<vector<int>> merge(vector<vector<int>>& intervals) {
    vector<vector<int>> ans;

    ranges::sort(intervals);

    for (const vector<int>& interval : intervals)
      if (ans.empty() || ans.back()[1] < interval[0])
        ans.push_back(interval);
      else
        ans.back()[1] = max(ans.back()[1], interval[1]);

    return ans;
  }
};

Đây là một đoạn mã C++ để hợp nhất các khoảng thời gian chồng chéo trong một mảng và trả về một mảng chứa các khoảng thời gian không chồng chéo.

Hàm `merge` nhận đầu vào là một vector 2D `intervals` chứa các khoảng thời gian. Nó trả về một vector 2D `ans` chứa các khoảng thời gian đã được hợp nhất.

Đầu tiên, một vector 2D `ans` rỗng được khởi tạo để lưu trữ các khoảng thời gian đã hợp nhất.

Sau đó, mảng `intervals` được sắp xếp theo thứ tự tăng dần của giá trị `start` của mỗi khoảng thời gian. Điều này giúp đảm bảo rằng các khoảng thời gian sẽ được xử lý theo thứ tự từ trái sang phải.

Trong vòng lặp `for`, mỗi khoảng thời gian `interval` trong `intervals` được xem xét. Nếu `ans` là một vector rỗng hoặc khoảng thời gian cuối cùng trong `ans` không chồng chéo với `interval`, nghĩa là `ans.back()[1] < interval[0]`, thì `interval` được thêm vào `ans` là một khoảng thời gian không chồng chéo mới. Ngược lại, nếu có sự chồng chéo, khoảng thời gian cuối cùng trong `ans` được cập nhật để bao gồm cả khoảng thời gian `interval` bằng cách so sánh và chọn giá trị lớn hơn giữa `ans.back()[1]` và `interval[1]`.

Cuối cùng, hàm trả về vector `ans` chứa các khoảng thời gian đã được hợp nhất.

Đây là một cách tiếp cận để hợp nhất các khoảng thời gian chồng chéo bằng cách sắp xếp và xử lý từng khoảng thời gian theo thứ tự.

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

class Solution {
  public int[][] merge(int[][] intervals) {
    List<int[]> ans = new ArrayList<>();

    Arrays.sort(intervals, (a, b) -> (a[0] - b[0]));

    for (int[] interval : intervals)
      if (ans.isEmpty() || ans.get(ans.size() - 1)[1] < interval[0])
        ans.add(interval);
      else
        ans.get(ans.size() - 1)[1] = Math.max(ans.get(ans.size() - 1)[1], interval[1]);

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

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

class Solution:
  def merge(self, intervals: List[List[int]]) -> List[List[int]]:
    ans = []

    for interval in sorted(intervals):
      if not ans or ans[-1][1] < interval[0]:
        ans.append(interval)
      else:
        ans[-1][1] = max(ans[-1][1], interval[1])

    return ans