从左至右对区间进行排序,因为D满足单调性,即如果D可以,D-1一定可以。所以可以在分隔距离D上进行二分答案。
对于固定的D,我们要检查是否可以放置至少N个玩偶。这可以通过贪心的策略来完成。只需将每个玩偶放在最左边的位置即可。一旦奶牛数量达到N,就可以break了,因此可以在O(N + M)时间检查一个D。
所以复杂度为O((N + M)log(max dist))。
/** * struct Interval { * int start; * int end; * }; */ #define LL long long #define INF 2000000000 #define X start #define Y end int nn, mm; vector<Interval> a; bool ok(int d) { LL prev = -1LL * INF * INF; int cnt = 0; for(int kk = 0; kk < a.size(); kk ++) { Interval i = a[kk]; while (max(prev + d, (LL)i.X) <= i.Y) { prev = max(prev + d, (LL)i.X); cnt++; if (cnt >= nn) break; } if (cnt >= nn) break; } return (cnt >= nn); } bool cmp(Interval x, Interval y) { if(x.X == y.X) return x.Y < y.Y; return x.X < y.X; } class Solution { public: /** * * @param n int整型 玩偶数 * @param m int整型 区间数 * @param intervals Interval类vector 表示区间 * @return int整型 */ int doll(int n, int m, vector<Interval>& intervals) { // write code here sort(intervals.begin(), intervals.end(), cmp); a.resize(m); nn = n; for(int kk = 0; kk < intervals.size(); kk ++) a[kk] = intervals[kk]; int lo = 1; int hi = INF; int res = -1; while (lo <= hi) { int mid = (lo + hi) / 2; if (ok(mid)) { res = mid; lo = mid + 1; } else { hi = mid - 1; } } return res; } };