目录

牛客_AB31活动安排_区间贪心

题目解析

C++代码

Java代码

---

牛客_AB31活动安排_区间贪心

活动安排_牛客题霸_牛客网

描述：

        给定n个活动，每个活动安排的时间为[ai,bi)。求最多可以选择多少个活动，满足选择的活动时间两两之间没有重合。

输入描述：

第一行输入一个整数nn (1≤n≤2⋅10^5)，表示可选活动个数。
接下来的n行，每行输入两个整数ai,bi (0≤ai<bi≤10^9)，表示第i个活动的时间。

输出描述：

输出一行一个整数，表示最多可选择的活动数。

---

题目解析

区间问题的贪心：排序，然后分情况讨论，看看是合并还是求交集。

C++代码

#include <asm-generic/errno.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;#define int long long
signed main()
{int n = 0;cin >> n;vector<vector<int>> arr(n, vector<int>(2));int maxTime = 0;for(int i = 0; i < n; ++i){cin >> arr[i][0] >> arr[i][1];maxTime += arr[i][1];}auto cmp = [=](vector<int> arr1, vector<int> arr2){if(arr1[0] < arr2[0])return true;else if(arr1[0] == arr2[0] && arr1[1] < arr2[1])return true;return false;};// sort(arr.begin(), arr.end(), cmp);sort(arr.begin(), arr.end()); // 不用自己写排序？确实，脑子瓦特了// for(int i = 0; i < n; ++i)// {//     cout << arr[i][0] << " " << arr[i][1] << endl;// }int res = 1;int last = arr[0][1];for(int i = 1; i < n; ++i){if(arr[i][0] >= last) // 没有重叠{++res;last = arr[i][1];}else // 有重叠 // 容易少这一句！！！！！！{last = min(last, arr[i][1]);}}cout << res << endl;// sort(arr.begin(), arr.end());// vector<vector<int>> dp(n + 1, vector<int>(maxTime));// // dp[i][j] 表示从1到i中选，活动时间不超过j的活动数？// int res = 0;// for(int i = 2; i <= n; ++i)// {//     for(int j = 0; j <= maxTime; ++j)//     {//         dp[i][j] = dp[i - 1][j]; // 不选//         if(j >= arr[i][1] && arr[i][0] >= arr[i - 1][1])//         {//             dp[i][j] = max(dp[i][j], dp[i][j - arr[i][1]] + 1); // 选//         }//         res = max(res, dp[i][j]);//     }// }// // cout << res << endl;// cout << 2 << endl;return 0;
}

Java代码

import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int[][] arr = new int[n][2];for(int i = 0; i < n; i++){arr[i][0] = in.nextInt();arr[i][1] = in.nextInt();}Arrays.sort(arr, (a, b) -> {return a[0] <= b[0] ? -1 : 1;});int ret = 0, r = arr[0][1];for(int i = 1; i < n; i++){if(arr[i][0] < r) // 有重叠{r = Math.min(r, arr[i][1]);}else // 没有重叠{ret++;r = arr[i][1];}}System.out.println(ret + 1);}
}