每日一题：不相交线段的最小最大值

题意

在一维数轴上给出 $m$ 个线段，每个线段都都有 $l,r,w$ 三个数据代表这个线段的左右端点和这个区间权值。 从中取出若干个不相交的线段(区间端点可以共用)，在覆盖满 $[1,n]$ 的情况下，取出的线段中 $权重的最大值]$ 最小能为多少？

Solution

$dp[i]$ 代表覆盖满 $[1,i]$ 最大权值最小为多少，然后按左端点从小到大枚举线段，就有 $dp[r_i]=min(dp[r_i],max(dp[l_i],w_i))$。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Node {
  int l, r;
  ll w;
} q[200005];

bool cmp(Node x, Node y) { return x.l < y.l; }

ll dp[100005];

int main() {
  int n, m;
  while (~scanf("%d%d", &n, &m)) {
    for (int i = 1; i <= m; i++) scanf("%d%d%lld", &q[i].l, &q[i].r, &q[i].w);
    sort(q + 1, q + m + 1, cmp);
    for (int i = 0; i <= n; i++) dp[i] = 1e18;
    dp[1] = 0;
    for (int i = 1; i <= m; i++)
      dp[q[i].r] = min(dp[q[i].r], max(dp[q[i].l], q[i].w));
    if (dp[n] == 1e18)
      puts("invalid data");
    else
      printf("%lld\n", dp[n]);
  }
  return 0;
}