结构体快排+贪心

#include<bits/stdc++.h>
using namespace std;
#define re register
#define vv vector
#define int long long
#define P pair<int,int>
const int MOD = 100003;
const int N = 1e4 + 5;

int n, l, res;
struct node {
	int s, e;
}m[N];


void solve()
{
	cin >> n >> l;
	for (int i = 0; i < n; i++) cin >> m[i].s >> m[i].e;
	auto cmp = [&](auto p1, auto p2) {
		return p1.s < p2.s;
		};
	sort(m, m + n, cmp);
	//start表示起始位置，end表示末尾位置
	int start = m[0].s;
	int end = m[0].e;
	for (int i = 1; i < n; i++) {
		//相邻两段重叠
		//[1.........10]
		//[   2...8    ]
		if (m[i].s <= end) end = max(end, m[i].e);
		else {//不重叠
			int gap = end - start;
			int cnt = gap / l;
			if (gap % l) cnt++;//不能整除，cnt向上取整
			start = max(start + cnt * l, m[i].s);
			end = max(start, m[i].e);//以防start+cnt*l后直接跨过了一个区间
			res += cnt;
		}
	}
    //处理最后一段区间
	res += (end - start) / l;
	if ((end - start) % l) res++;
	cout << res;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}