LeetCode 冥想：不重叠的区间

非重叠间隔的描述是：

给定一个间隔数组，其中间隔[i] = [start_i, end_i]，返回需要删除以使其余间隔不重叠的最小间隔数。

注意仅在一个点接触的间隔不重叠。例如，[1, 2] 和 [2, 3] 不重叠。

例如：

Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1

Explanation: [1, 3] can be removed and the rest of the intervals are non-overlapping.

或者：

Input: intervals = [[1, 2], [1, 2], [1, 2]]
Output: 2

Explanation: You need to remove two [1, 2] to make the rest of the intervals non-overlapping.

或者：

Input: intervals = [[1, 2], [2, 3]]
Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

---

对于这个问题，NeetCode 有一个很好的解决方案，从对间隔进行排序开始，就像我们在上一个问题中所做的那样。
我们还可以初始化一个变量来跟踪删除的数量。

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

let numRemovals = 0;

现在我们的间隔已排序，我们将遍历每个间隔，检查它们是否重叠。为此，我们将跟踪前一个间隔的 end，因此让我们初始化一个 prevEnd 变量，该变量最初保存第一个间隔的结束：

let prevEnd = intervals[0][1];

注意 标题> 对于两个间隔

Note

For two intervals not to overlap, the start of one should be strictly larger than the end of the other or the end of the one should be strictly smaller than the start of the other, as mentioned in our chapter introduction.

不重叠的情况，其中一个的开始应该严格大于，结束其他或其中一个的结尾应该严格 小于另一个的开始，如我们章节介绍中所述。 表>

在此问题中，当一个间隔的结束位置等于另一个间隔的开始位置时，它们被视为不重叠。

因此，在这里我们可以说，如果一个间隔的开始严格小于另一个间隔的结束，则两个间隔将重叠。在这种情况下，我们会将 prevEnd 更新为两端的较小值，以便与下一个间隔重叠的机会较小。否则，我们将像以前一样继续：

Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1

Explanation: [1, 3] can be removed and the rest of the intervals are non-overlapping.

最后，我们可以返回 numRemovals:

Input: intervals = [[1, 2], [1, 2], [1, 2]]
Output: 2

Explanation: You need to remove two [1, 2] to make the rest of the intervals non-overlapping.

并且，我们的最终解决方案如下所示：

Input: intervals = [[1, 2], [2, 3]]
Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

时间和空间复杂度

由于我们在开始时对间隔进行排序，时间复杂度将为 $O(nlogn）$O(n log n) 。我们没有额外的数据结构，其大小会随着输入大小的增加而增加，因此空间复杂度为 $O(1)$O(1) .

---

接下来，我们将开始该系列的最后一章，位操作。在那之前，祝您编码愉快。

以上是LeetCode 冥想：不重叠的区间的详细内容。更多信息请关注PHP中文网其他相关文章！