Round F 2020 - Kick Start 2020

题意：N个interval的工作（si, ei），不重叠，K表示机器人可以连续工作的时间，比如S开始，机器人在S+K时间段内都在工作。求最少启动多少次机器人可以完成所有的interval的工作，机器人一次只能做一个工作。

---

思路：因为interval不重叠，首先将interval按照起始时间排序，然后贪心启动机器人。

---

C++代码：

#include <stdio.h>

#include <iostream>

#include <map>

using namespace std;

map<int, int> mp;

int main(){

    int T;

    cin >> T;

    for(int t = 1; t <= T; t++){

        mp.clear();

        int n, k;

        cin >> n >> k;

        for(int i = 0; i < n; i++){

            int s, e;

            cin >> s >> e;

            mp[s] = e;

        }

        int ed = -1;

        int res = 0;

        for(auto it = mp.begin(); it != mp.end(); it++){

            if(ed == -1) ed = it->first;

            if(it->first > ed) ed = it->first;

            if(it->second > ed){

                int c = (it->second - ed) / k;

                ed = ed + c * k;

                res += c;

                if(it->second > ed){

                    ed += k;

                    res++;

                }

            }

        }

        printf("Case #%d: %d\n", t, res);

    }

}