вопрос с ошибками
как дела(английский: жадный алгоритм), также известный как жадностьалгоритм, это выбор, который берет лучшее или оптимальное (т.е. наиболее благоприятное) в текущем состоянии на каждом шаге выбора, надеясь привести к лучшему или оптимальному результатуалгоритм. Например, в задаче коммивояжера, если путешественник каждый раз выбирает ближайший город, то этокак дела.
описывать
Учитывая набор интервалов, найдите минимальное количество интервалов, которые нужно удалить, чтобы оставшиеся интервалы не перекрывали друг друга.
Уведомление:
- Можно считать, что конечная точка интервала всегда больше его начальной точки.
- Границы интервалов [1,2] и [2,3] «касаются» друг друга, но не перекрывают друг друга.
Пример 1:
输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
输入: [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
输入: [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
решение проблем
Сначала выполняется сортировка, и отсортированные данные легче сравнивать, в противном случае массив необходимо часто обходить в неупорядоченном состоянии.
- Сортировка, сначала сортировка по начальной точке и сравнение конечной позиции, если начальная позиция такая же.
- После сортировки может возникнуть несколько ситуаций. Есть 5 случаев, как показано ниже.
- Случай 1, перекрытие A1.start
- Случай 2, перекрытие A1.strat A2.end
- Случай 3, перекрытие A1.strat
- Случай 4, неперекрывающиеся A2.start >= A1.end
- Случай 5, перекрывающийся A1.start=A2.start && A1.end A2.end
- Помимо оценки наличия перекрытия, необходимо учитывать еще один фактор.Найдите минимальное количество интервалов, которые нужно удалить., то в вышеперечисленных 5 случаях какой целесообразнее удалить? Удалить A1 или A2
- Случай 1, удалите A2, так как A2, скорее всего, перекроет элементы позади
- Случай 2, удалите A1, потому что A1 занимает больше места, и возможность перекрытия с A1 больше, чем у A2
- Случай 3, удалить A1 по той же причине, что и выше
- Случай 4, не перекрывающиеся, обработка не требуется
- Случай 5, удалите A2, A2, скорее всего, перекроет элементы сзади.
кодирование
- Сначала отсортируйте.
// 对数组排序，从小到大排序，首先比较start，再比较end
// 排序前 [ [1,2], [2,3], [3,4], [1,3] ]
// 排序后 [ [1,2], [1,3]，[2,3], [3,4] ]
Arrays.sort(intervals, new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
if (o1.start == o2.start) {
return o1.end - o2.end;
}
return o1.start - o2.start;
}
});
- Рассмотрим различные ситуации с обработкой элементов. Обработка ситуации на этом этапе согласуется с приведенным выше анализом, просто необходимо понять приведенные выше идеи решения проблем.
// 当前需要被比较的Interval坐标
int currentIndex = 0;
// 重复区间的个数
int count = 0;
for (int i = 1; i < intervals.length; i++) {
// 情况1
// currentIndex [=====]
// intervals[i] [=====]
boolean overLapFlag = false;
if (intervals[currentIndex].end <= intervals[i].end && intervals[i].start < intervals[currentIndex].end) {
count++;
overLapFlag = true;
}
// 情况2 && 情况3
// currentIndex [=====]
// intervals[i] [==]
else if (intervals[currentIndex].end >= intervals[i].end) {
count++;
overLapFlag = true;
}
// 情况 5 ，因为已经排好序了，所以后续元素肯定大于前一个
// currentIndex [====]
// intervals[i] [======]
else if (intervals[currentIndex].start == intervals[i].start) {
count++;
overLapFlag = true;
}
// 当某个元素占的空间太大的时候，考虑换一下位置
// 判断条件同条件2
if (overLapFlag){
if (intervals[currentIndex].end >= intervals[i].end)
{
System.out.println("替换元素：currentIndex" + intervals[currentIndex] + "~" + intervals[i]);
currentIndex = i;
}
continue;
}
// 最后一种
// currentIndex [====]
// intervals[i] [===]
currentIndex = i;
}
- Сводка кода
public static int eraseOverlapIntervals(Interval[] intervals) {
if (intervals.length == 0 || intervals.length == 1) {
return 0;
}
// 对数组排序，从小到大排序，首先比较start，再比较end
// 排序前 [ [1,2], [2,3], [3,4], [1,3] ]
// 排序后 [ [1,2], [1,3]，[2,3], [3,4] ]
Arrays.sort(intervals, new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
if (o1.start == o2.start) {
return o1.end - o2.end;
}
return o1.start - o2.start;
}
});
// 当前需要被比较的Interval坐标
int currentIndex = 0;
// 重复区间的个数
int count = 0;
// for (int i = 0; i < intervals.length; i++) {
// System.out.println("[" + intervals[i].start + "," + intervals[i].end + "]");
// }
for (int i = 1; i < intervals.length; i++) {
// 情况1
// currentIndex [=====]
// intervals[i] [=====]
boolean overLapFlag = false;
if (intervals[currentIndex].end <= intervals[i].end && intervals[i].start < intervals[currentIndex].end) {
count++;
overLapFlag = true;
}
// 情况2 && 情况3
// currentIndex [=====]
// intervals[i] [==]
else if (intervals[currentIndex].end >= intervals[i].end) {
count++;
overLapFlag = true;
}
// 情况 5 ，因为已经排好序了，所以后续元素肯定大于前一个
// currentIndex [====]
// intervals[i] [======]
else if (intervals[currentIndex].start == intervals[i].start) {
count++;
overLapFlag = true;
}
// 当某个元素占的空间太大的时候，考虑换一下位置
// 判断条件同条件2
if (overLapFlag){
if (intervals[currentIndex].end >= intervals[i].end)
{
System.out.println("替换元素：currentIndex" + intervals[currentIndex] + "~" + intervals[i]);
currentIndex = i;
}
continue;
}
// 最后一种
// currentIndex [====]
// intervals[i] [===]
currentIndex = i;
}
return count;
}
- Результаты
дополнительный
Также есть жадный алгоритм, который сравнивает только количество неповторяющихся элементов, а остальные удаляются, сравнивается только четвертый случай.
Как показано на рисунке:
- Если начало А1 маленькое, а конец очень длинный, многие элементы будут упущены.
Следовательно, также необходимо оценить, не является ли текущий элемент слишком длинным. содержит предыдущий элемент
Идея заключается в следующем:
public static int eraseOverlapIntervalsV2(Interval[] intervals) {
if (intervals.length == 0 || intervals.length == 1) {
return 0;
}
// 对数组排序，从小到大排序，首先比较start，再比较end
// 排序前 [ [1,2], [2,3], [3,4], [1,3] ]
// 排序后 [ [1,2], [1,3]，[2,3], [3,4] ]
Arrays.sort(intervals, new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
if (o1.start == o2.start) {
return o1.end - o2.end;
}
return o1.start - o2.start;
}
});
// 当前需要被比较的Interval坐标
int currentIndex = 0;
// 重复区间的个数
int count = 1;
for (int i = 1; i < intervals.length; i++) {
// 最后一种
// currentIndex [====]
// intervals[i] [===]
if (intervals[i].start >= intervals[currentIndex].end){
count++;
currentIndex = i;
}
else {
if (intervals[i].end <= intervals[currentIndex].end){
currentIndex=i;
}
}
}
return intervals.length - count;
}
По сути, это то же самое, что и предыдущий шаг.
Наконец
Ясное мышление может написать элегантный код