LeetCode 명상: 간격 삽입

삽입 간격에 대한 설명은 매우 명확합니다.

간격[i] = [start_i, end_i]가 i번째 간격의 시작과 끝을 나타내고 간격이 start_i를 기준으로 오름차순으로 정렬되는 중첩되지 않는 간격의 배열이 제공됩니다. 또한 다른 간격의 시작과 끝을 나타내는 newInterval = [start, end] 간격도 제공됩니다.

간격이 여전히 start_i에 의해 오름차순으로 정렬되고 간격에 겹치는 간격이 없도록 newInterval을 간격에 삽입합니다(필요한 경우 겹치는 간격 병합).

반환 간격삽입 후.

참고 간격을 내부에서 수정할 필요는 없습니다. 새로운 배열을 만들어서 반납하시면 됩니다.

예:

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

또는:

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].

---

결과를 담을 결과 배열을 만드는 것부터 시작할 수 있습니다.

let result = [];

그런 다음 모든 간격을 검토하면서 새 간격을 현재 간격 앞이나 뒤에 두어야 하는지, 또는 겹쳐서 병합해야 하는지 확인해야 합니다.

장 소개에서 본 것처럼 두 간격은 겹치지 않습니다 한 간격의 시작이 다른 간격의 끝보다 엄격하게 크거나 한쪽의 끝이 엄격하게 작은 경우 상대방의 시작보다.

두 사례가 모두 거짓인 경우 중복됩니다.

먼저 newInterval이 간격보다 먼저 오는지 확인할 수 있습니다. 실제로 이 항목(newInterval을 배치하기 위해 찾을 수 있는 "가장 빠른" 위치)을 먼저 확인하면 새로 구성된 결과로 즉시 반환할 수 있습니다.
이것도 욕심 접근 방식입니다.

for (let i = 0; i < intervals.length; i++) {
  const interval = intervals[i];

  // newInterval is before interval
  if (newInterval[1] < interval[0]) {
    result.push(newInterval);
    return [...result, ...intervals.slice(i)];
  }
  /* ... */  
}

그러나 newInterval이 우리가 보고 있는 현재 간격 뒤에 오면 현재 간격을 결과로 푸시할 수 있습니다.

for (let i = 0; i < intervals.length; i++) {
  /* ... */
  // newInterval is after interval
  else if (newInterval[0] > interval[1]) {
    result.push(interval);
  }
}

마지막 옵션은 겹치는 경우입니다. 이 경우 두 간격을 병합해야 합니다. 간격의 최소값을 시작으로 하고 최대값을 새 간격의 끝으로 사용하여 newInterval을 다시 생성할 수 있습니다.

for (let i = 0; i < intervals.length; i++) {
  /* ... */
  // overlapping, create newInterval
  else {
    newInterval = [
      Math.min(newInterval[0], interval[0]),
      Math.max(newInterval[1], interval[1])
    ];
  }
}

현재 루프는 다음과 같습니다.

for (let i = 0; i < intervals.length; i++) {
  const interval = intervals[i];

  // newInterval is before interval
  if (newInterval[1] < interval[0]) {
    result.push(newInterval);
    return [...result, ...intervals.slice(i)] 

  // newInterval is after interval
  } else if (newInterval[0] > interval[1]) {
    result.push(interval);

  // overlapping, create newInterval
  } else {
    newInterval = [Math.min(newInterval[0], interval[0]), Math.max(newInterval[1], interval[1])];
  }
}

또한 우리가 만든 최신 newInterval을 푸시해야 합니다. 그리고 마지막에는 결과를 반환할 수 있습니다.

function insert(intervals: number[][], newInterval: number[]): number[][] {
  /* ... */
  result.push(newInterval);
  return result;
}

마지막으로 솔루션은 다음과 같습니다.

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

시간과 공간의 복잡성

시간복잡도는 $O(n)$O(n) 간격 배열의 각 항목에 대해 지속적인 작업을 수행합니다. 공간 복잡도는 $O(n)$O(n) 또한 결과 배열을 유지하며 간격 길이가 증가함에 따라 크기도 증가합니다.

---

다음으로 병합 간격을 살펴보겠습니다. 그때까지 즐거운 코딩하세요.

위 내용은 LeetCode 명상: 간격 삽입의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!