贪心算法入门——区间问题

题目均来自acwing.com

AcWing 905. 区间选点

给定 N 个闭区间 [ai,bi],请你在数轴上选择尽量少的点,使得每个区间内至少包含一个选出的点。输出选择的点的最小数量。

思路:每个区间迟早要选出一个符合要求的点,而对于一个大区间包含小区间的情况,小区间满足大区间一定满足,反之不亦然,所以不妨先考虑小区间。
按右端点从小到大排序。首先考虑第一个区间,反正一定要选一个点,不妨选右端点,显然,这样能尽可能覆盖较多(左端点在第一段右端点的左边的)区间,把这个点设为pos。依次枚举每一个区间,如果它的左端点小于等于pos,则一定已经被覆盖了;如果他的左端点大于等于pos,则需要选一个新点,同理可知应该选右端点,重复上述过程即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
struct Seg {
  int l, r;
}seg[N];

bool cmp(Seg a, Seg b) {
  if (a.r != b.r) return a.r < b.r;
  else return a.l > b.l;
}

int main() {
  cin >> n;
  for (int i = 0; i < n; i++) cin >> seg[i].l >> seg[i].r;
  sort(seg, seg + n, cmp);
  int ans = 1, pos = seg[0].r;
  for (int i = 1; i < n; i++) 
    if (seg[i].l > pos) ans++, pos = seg[i].r;
  cout << ans;
  return 0;
}

AcWing 908. 最大不相交区间数量

给定 N 个闭区间 [ai,bi],请你在数轴上选择若干区间,使得选中的区间之间互不相交(包括端点)。输出可选取区间的最大数量。

思路:首先考虑第一个区间选哪个。按右端点从小到大排序,选择右端点最小的区间,可以尽可能地提高选择的余地。在数轴剩下的部分同样这样做即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;

struct Seg {
  int l, r;
} seg[N];

bool cmp(Seg a, Seg b) {
  return a.r < b.r;
}
int main() {
  cin >> n;
  for (int i = 0; i < n; i++) cin >> seg[i].l >> seg[i].r;
  sort(seg, seg + n, cmp);
  int ans = 1, pos = seg[0].r;
  for (int i = 1; i < n; i++) 
    if (seg[i].l > pos) ans++, pos = seg[i].r;
  cout << ans;
  return 0;
}

AcWing 906. 区间分组

给定 N 个闭区间 [ai,bi],请你将这些区间分成若干组,使得每组内部的区间两两之间(包括端点)没有交集,并使得组数尽可能小。

思路:
图书馆中最少需要安排多少个座位,使得N个在不同时段[ai,bi]学习的人恰好都有座?
只要座位数大于同时学习的最大人数即可。。。(反正每个来到的人都会自动坐在空位上。。。)
我也不知道这叫啥思路,“人工智能”?
用差分+前缀和的话,数组有点大,自然想到离散化。
其实没必要,将“坐下”和“离开”的所有操作按时间先后排序,按照时间轴依次进行(座位+1/-1)即可。
同一个时间点既有来学习的也有离开的,需要为来学习的人加一个座位。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
struct Seg {
  int l, r;
}seg[N];

bool cmp(Seg a, Seg b) {
  if (a.r != b.r) return a.r < b.r;
  else return a.l > b.l;
}

int main() {
  cin >> n;
  for (int i = 0; i < n; i++) cin >> seg[i].l >> seg[i].r;
  sort(seg, seg + n, cmp);
  int ans = 1, pos = seg[0].r;
  for (int i = 1; i < n; i++) 
    if (seg[i].l > pos) ans++, pos = seg[i].r;
  cout << ans;
  return 0;
}

AcWing 907. 区间覆盖

给定 N 个闭区间 [ai,bi] 以及一个线段区间 [s,t],请你选择尽量少的区间,将指定线段区间完全覆盖。输出最少区间数,如果无法完全覆盖则输出 ?1。

思路:
首先考虑覆盖了s点的区间,显然要选右端点最靠右的。
将所选区间的右端点当作新的s继续操作即可。
扫一遍即可,具体实现见代码。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int inf = 0x3f3f3f3f;
int n, s, t;
struct Seg {
  int l, r;
} seg[N];

bool cmp(Seg a, Seg b) {
  return a.l < b.l;
}
int main() {
  cin >> s >> t >> n;
  for (int i = 0; i < n; i++) {
    cin >> seg[i].l >> seg[i].r;
  }
  sort(seg, seg + n, cmp);
  int pos = s, maxr = -inf, ans = 0;
  for (int i = 0; i < n; i++) {
    if (seg[i].l > pos) pos = maxr, ans++;
    if (seg[i].l <= pos && seg[i].r >= pos && seg[i].r > maxr) {
      maxr = seg[i].r;
    }
    if (pos >= t) break;
  }
  if (pos < t && maxr >= t) pos = maxr, ans++;
  if (pos >= t) cout << ans;
  else cout << -1;
  return 0;
}

贪心算法入门——区间问题

上一篇:libtorch 数组索引和张量操作 与pytorch比较


下一篇:js基础---forEach遍历数组