原题链接

题目描述

一家餐厅收到了 nn 个客人的预约订单。

每个订单都有开始时间和结束时间。

对于每个订单，餐厅有权利接单，也有权利拒单。

接受的订单，两两之间不得有任何时间交集，甚至不得有时刻交集，即如果一个订单的开始时间和另一个订单的结束时间相同，则两订单也不得同时接受。

为了赚更多钱，餐厅需要尽可能多的接单。

请问，餐厅最多可以接多少单？

输入格式

第一行包含一个整数 nn。

接下来 nn 行，每行包含两个整数 l,rl,r，表示一个订单的开始时间和结束时间。

输出格式

输出可以接受的最大订单数量。

数据范围

1≤n≤5×1051≤n≤5×10^5,
1≤l≤r≤1091≤l≤r≤10^9

样例

输入样例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+1 。

代码

C++

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 5 * 1e5 + 5;

struct Order
{
    int l, r;
    
    bool operator < (const Order &o) const
    {
        return this->r < o.r;
    }
}o[N];

int main()
{
    int n;
    scanf("%d", &n);
    for ( int i = 0; i < n; i ++ )
        scanf("%d %d", &o[i].l, &o[i].r);
    sort(o, o + n);
    int res = 0, last = 0;
    for ( int i = 0; i < n; i ++ )
        if ( last < o[i].l ) res ++, last = o[i].r;
    printf("%d\n", res);
    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main
{
    private static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    
    private static class Order
    {
        int l, r;
        
        public Order(int l, int r)
        {
            this.l = l;
            this.r = r;
        }
    }
    
    public static void main(String args[]) throws Exception
    {
        int n = Integer.parseInt(in.readLine());
        Order order[] = new Order[n];
        for ( int i = 0; i < n; i ++ )
        {
            String w[] = in.readLine().split(" ");
            order[i] = new Order(Integer.parseInt(w[0]), Integer.parseInt(w[1]));
        }
        Arrays.sort(order, (a, b) -> a.r - b.r);
        int res = 0, last = 0;
        for ( int i = 0; i < n; i ++ )
            if ( last < order[i].l )
            {
                res ++;
                last = order[i].r;
            }
        System.out.printf("%d\n", res);
    }
    
}