non-overlapping-intervals

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given an array of intervals <code>intervals</code> where <code>intervals[i] = [starti, endi]</code>, return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note that intervals which only touch at a point are non-overlapping. For example, <code>[1, 2]</code> and <code>[2, 3]</code> are non-overlapping.

&nbsp;
Example 1:

<pre>
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.
</pre>

Example 2:

<pre>
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.
</pre>

Example 3:

<pre>
Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don&#39;t need to remove any of the intervals since they&#39;re already non-overlapping.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= intervals.length &lt;= 105</code></li>
	<li><code>intervals[i].length == 2</code></li>
	<li><code>-5 * 104 &lt;= starti &lt; endi &lt;= 5 * 104</code></li>
</ul>

eraseOverlapIntervals

Non-overlapping Intervals

Minimum Number of Arrows to Burst Balloons

minimum-number-of-arrows-to-burst-balloons

用最少数量的箭引爆气球

Determine if Two Events Have Conflict

determine-if-two-events-have-conflict

判断两个事件是否存在冲突

Greedy

Array

Dynamic Programming

Sorting

给定一个区间的集合&nbsp;<code>intervals</code>&nbsp;，其中 <code>intervals[i] = [starti, endi]</code>&nbsp;。返回 需要移除区间的最小数量，使剩余区间互不重叠&nbsp;。

注意&nbsp;只在一点上接触的区间是&nbsp;不重叠的。例如&nbsp;<code>[1, 2]</code>&nbsp;和&nbsp;<code>[2, 3]</code>&nbsp;是不重叠的。

&nbsp;

示例 1:

<pre>
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
</pre>

示例 2:

<pre>
输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
</pre>

示例 3:

<pre>
输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
</pre>

&nbsp;

提示:

<ul>
	<li><code>1 &lt;= intervals.length &lt;= 105</code></li>
	<li><code>intervals[i].length == 2</code></li>
	<li><code>-5 * 104&nbsp;&lt;= starti&nbsp;&lt; endi&nbsp;&lt;= 5 * 104</code></li>
</ul>

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier! Saves Data!