题目描述
一家餐厅收到了 n 个客人的预约订单。
每个订单都有开始时间和结束时间。
对于每个订单,餐厅有权利接单,也有权利拒单。
接受的订单,两两之间不得有任何时间交集,甚至不得有时刻交集,即如果一个订单的开始时间和另一个订单的结束时间相同,则两订单也不得同时接受。
为了赚更多钱,餐厅需要尽可能多的接单。
请问,餐厅最多可以接多少单?
输入格式
第一行包含一个整数 n。
接下来 n 行,每行包含两个整数 l,r,表示一个订单的开始时间和结束时间。
输出格式
输出可以接受的最大订单数量。
数据范围
1≤n≤5×105,
1≤l≤r≤109
样例
输入样例1:
2
7 11
4 7
输出样例1:
1
输入样例2:
5
1 2
2 3
3 4
4 5
5 6
输出样例2:
3
输入样例3:
6
4 8
1 5
4 7
2 5
1 3
6 8
输出样例3:
2
算法1
(排序+一次遍历) $O(nlog(n))$
1.按照右端点排序
2.时间卡得有点紧
3.python3 nums中存放[]就超时 ()就AC
c++ pair + cin超时 –> class Node public + scanf就AC –> struct Node +scanf 就很快
java scan 超时, br才AC
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int n; cin >> n;
vector<pair<int, int>> nums(n);
for (int i = 0; i < n; i ++)
{
cin >> nums[i].first;
cin >> nums[i].second;
}
sort(nums.begin(), nums.end(), [&](const auto & a, const auto & b)
{
return a.second < b.second;
});
int res = 0;
int rr = -1;
for (auto & [l, r] : nums)
{
if (rr < l)
{
res ++;
rr = r;
}
}
cout << res << endl;
return 0;
}
c++ 代码 次快
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
class Node
{
public:
int l;
int r;
Node()
{}
Node(int l_, int r_)
{
l = l_;
r = r_;
}
const bool operator < (const Node & rhs) const
{
return r < rhs.r;
}
};
int main()
{
int n;
scanf("%d", &n);
Node nums[n];
for (int i = 0; i < n; i ++)
{
scanf("%d%d", &nums[i].l, &nums[i].r);
}
sort(nums, nums + n);
int res = 0;
int rr = -1;
for (auto & node : nums)
{
if (rr < node.l)
{
res ++;
rr = node.r;
}
}
cout << res << endl;
return 0;
}
c++ 代码 最快
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 500010;
struct Node{
int l;
int r;
const bool operator < (const Node & rhs) const
{
return r < rhs.r;
}
} nums[N];
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++)
{
scanf("%d%d", &nums[i].l, &nums[i].r);
}
sort(nums, nums + n);
int res = 0;
int rr = -1;
for (auto & node : nums)
{
if (rr < node.l)
{
res ++;
rr = node.r;
}
}
cout << res << endl;
return 0;
}
python3 代码
import sys
n = int(input())
nums = []
for _ in range(n):
l, r = map(int, sys.stdin.readline().split())
nums.append((l, r))
nums.sort(key = lambda x : x[1])
res = 0
rr = -1
for l, r in nums:
if rr < l:
res += 1
rr = r
print(res)
java 代码
import java.util.* ;
import java.io.* ;
public class Main
{
public static void main(String [] args) throws Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int [][] nums = new int [n][2];
for (int i = 0; i < n; i ++)
{
String [] tmp1 = br.readLine().split(" ");
nums[i][0] = Integer.parseInt(tmp1[0]);
nums[i][1] = Integer.parseInt(tmp1[1]);
}
br.close();
Arrays.sort(nums, new Comparator<int []>(){
public int compare(int [] a, int [] b)
{
return a[1] - b[1];
}
});
int res = 0;
int rr = -1;
for (int i = 0; i < n; i ++)
{
int l = nums[i][0], r = nums[i][1];
if (rr < l)
{
res ++;
rr = r;
}
}
System.out.println(res);
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla