img

king-yyf

推荐算法 / 精排/混排

king-yyf

推荐算法er

mind and hand

区间计数与扫描线

| 阅读：次

===

Index

区间覆盖

会议室2

给你一个会议时间安排的数组 intervals, 每个会议 intervals[i] = [starti, endi] ，表示会议的开始和结束时间，返回所需会议室的最小数量。

  • 1 <= intervals.length() <= 1e4
  • 0 <= starti < endi <= 1e6

方法1

这题可以理解为上下公交车问题，不用在意是谁上车还是下车，只需要注意什么时候上下车就可以。 以第一个示例来说：

↑    ↑    ↓     ↑      ↓             ↓
0----5----10----15-----20-----------30-->


class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& a) {
        vector<pair<int,int> > v;
        for(auto& x: a) {
            v.push_back({x[0], 1});
            v.push_back({x[1], -1});
        }
        sort(v.begin(), v.end());
        int ans = 0, c = 0;
        for(auto &[x, y]: v) {
            c += y;
            ans = max(ans, c);
        }
        return ans;
    }
};

方法2:优先队列

  1. 按照 开始时间 对会议进行排序。
  2. 初始化一个新的 最小堆，将第一个会议的结束时间加入到堆中。我们只需要记录会议的结束时间，告诉我们什么时候房间会空。
  3. 对每个会议，检查堆的队首元素（即堆顶部的房间）是否空闲。。
    1. 若房间空闲，则从堆顶拿出该元素，直到房间不空闲或堆为空
    2. 将当前会议结束时间加入到堆中。
  4. 处理完所有会议后，处理过程中堆的最大大小即为需要的答案。
class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& a) {
        sort(a.begin(), a.end(), [](auto &x, auto &y){
            return x[0] < y[0];
        });
        priority_queue<int, vector<int>, greater<int>> q;
        int c = 0;
        for (int i = 0; i < a.size(); i++) {
            while (!q.empty() && q.top() <= a[i][0]) {
                q.pop();
            }
            q.push(a[i][1]);
            c = max(c, (int)q.size());
        }
        return c;
    }
};

每个人到达时花的数目

leetcode 周赛290 T4

给你一个下标从 0 开始的二维整数数组 flowers ，其中 flowers[i] = [starti, endi] 表示第 i 朵花的 花期 从 starti 到 endi （都包含）。同时给你一个下标从 0 开始大小为 n 的整数数组 persons ，persons[i] 是第 i 个人来看花的时间。

请你返回一个大小为 n 的整数数组 answer ，其中 answer[i]是第 i 个人到达时在花期内花的 数目 。

  • 1 <= flowers.length() <= 5 * 1e4
  • 1 <= persons.length <= 5 * 1e4
  • 1 <= persons[i] <= 1e9
  • 1 <= starti <= endi <= 1e9

方法1：排序

把 flowers[i] 分成两个点：(flowers[i][0], -1) 表示花期的开始，(flowers[i][1], -2) 表示花期的结束。每个询问也看成一个点 (persons[i], i)。

把所有点排序，维护变量 x，遇到花期开始则 x++，花期结束则 x–，询问则答案就是当前的 x 值。复杂度 O(nlog(n))。

class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& a, vector<int>& b) {
        vector<pair<int,int> > v;
        for(auto &x: a){
            v.push_back({x[0], -1});
            v.push_back({x[1] + 1, -2});
        } 
        int n = b.size(), x = 0;
        for (int i = 0; i < n; ++i) {
            v.push_back({b[i], i});;
        }
        sort(v.begin(), v.end());
        vector<int> c(n);
        for(auto &[k, v] : v) {
            if (v == -1) x++;
            else if (v == -2) x--;
            else c[v] = x;
        }
        return c;
    }
};

方法2：优先队列

  1. 将所有人按照到达时间排序
  2. 将花按照花期的开始时间排序，用优先队列从小到大维护花期的结束时间
  3. 遍历人到达时间数组，将所有开始时间早于到达时间的花的结束时间加入到优先队列，将所有花期结束时间小于当前时间的花从队列中删除。
  4. 优先队列的大小即为当前人到达时在花期内的花的数目

每个花期的结束时间最多只会入堆一次、出堆一次，时间复杂度为 O(nlog(n))

class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& a, vector<int>& b) {
        int n = a.size(), m = b.size();
        sort(a.begin(), a.end(), [](auto &x, auto &y){
            return x[0] < y[0];
        });
        priority_queue<int, vector<int>, greater<int>> q;
        vector<pair<int, int>> v;
        for (int i = 0; i < m; ++i) v.push_back({i, b[i]});
        sort(v.begin(), v.end(), [](auto &x, auto &y) {
            return x.second < y.second; 
        });
        for (int i = 0, j = 0; i < m; ++i) {
            while (j < n && a[j][0] <= v[i].second) {
                q.push(a[j++][1]);
            }
            while (!q.empty() && q.top() < v[i].second) q.pop();
            c[v[i].first] = q.size();
        }
        return c;
    }
};

被k个区间覆盖的点的数目

codeforces 1000c

给n个区间，[l1,r1],…,[ln,rn]. 返回一个长度为n的数组，第i个元素是被i个区间覆盖的点的数目

  • 1 <= n <= 2e5
  • 0 <= li <= ri <= 1e18
vector<long long> coverPointCount(vector<vector<long long>>& a) {
    int n = a.size(), cnt = 0;
    vector<pair<long long,int> > v;
    for (auto& e: a) {
        v.push_back({e[0], 1});
        v.push_back({e[1] + 1, -1});
    }
    sort(v.begin(), v.end());
    vector<long long> c(n);
    long long s = 0;
    for (auto &[x, y]: v) {
        if (cnt > 0) c[cnt - 1] += x - s;
        cnt += y;
        s = x;
    }
    return c;
}

会议室3

leetcode周赛309 T4

有n个会议室，编号0-(n-1),

给你一个二维整数数组 meetings ，其中 meetings[i] = [starti, endi] 表示一场会议将会在 半闭 时间区间 [starti, endi) 举办。所有 starti 的值 互不相同 。

会议将会按以下方式分配给会议室：

  • 每场会议都会在未占用且编号 最小 的会议室举办。
  • 如果没有可用的会议室，会议将会延期，直到存在空闲的会议室。延期会议的持续时间和原会议持续时间 相同 。
  • 当会议室处于未占用状态时，将会优先提供给原 开始 时间更早的会议。

返回举办最多次会议的房间 编号 。如果存在多个房间满足此条件，则返回编号 最小 的房间。

  • 1 <= n <= 100
  • 1 <= meetings.length <= 1e5
  • 0 <= starti < endi <= 5e5

分析

因为“当会议室处于未占用状态时，将会优先提供给原开始时间更早的会议”，因此有重要性质：会议开始的相对顺序不会改变。我们只需要按顺序模拟每个会议分配给哪个会议室即可。

int mostBooked(int n, vector<vector<int>>& a) {
        int m = a.size(), res = 0;
        sort(a.begin(), a.end());
        vector<int> c(n);
        vector<long long> t(n);
        for (int i = 0; i < m; ++i) {
            int pos = -1;
            for (int j = 0; j < n; ++j) if (t[j] <= a[i][0]) {
                pos = j; break;
            }
            if (pos != -1) {
                t[pos] = a[i][1];
                ++c[pos];
            } else {
                long long mx = 1e18;
                int p = -1;
                for (int j = 0; j < n; ++j) if (t[j] < mx)  mx = t[j], p = j;
                ++c[p];
                t[p] += a[i][1] - a[i][0];
            }
        }
        for (int i = 1; i < n; ++i) if (c[res] < c[i]) res = i;
        return res;
    }

二维偏序问题

二维偏序是这样一类问题：已知点对的序列 (a1,b1)…(an,bn) 并在其上定义某种偏序关系 < ， 现在有点 (ai,bi) ，求 满足 ‘(aj,bj) < (ai,bi)’ 的 (aj,bj)数量。

统计包含每个点的矩形数目

leetcode 周赛90 T3

给你一个二维整数数组 rectangles ，其中 rectangles[i] = [li, hi] 表示第 i 个矩形长为 li 高为 hi 。给你一个二维整数数组 points ，其中 points[j] = [xj, yj] 是坐标为 (xj, yj) 的一个点。

第 i 个矩形的 左下角 在 (0, 0) 处，右上角 在 (li, hi) 。

请你返回一个整数数组 count ，长度为 points.length，其中 count[j]是 包含 第 j 个点的矩形数目。

如果 0 <= xj <= li 且 0 <= yj <= hi ，那么我们说第 i 个矩形包含第 j 个点。如果一个点刚好在矩形的 边上 ，这个点也被视为被矩形包含。

二维偏序问题，可以用树状数组解决

如果 x 或者 y 范围都比较大，在建立树状数组时需要对某一维进行离散化。

class Solution {
    const int INF = 1e9;
    int n;
    vector<int> tr;

    void add(int p) {
        for (; p <= n; p += p & (-p)) tr[p]++;
    }

    int query(int p) {
        int ret = 0;
        for (; p; p -= p & (-p)) ret += tr[p];
        return ret;
    }

public:
    vector<int> countRectangles(vector<vector<int>>& rs, vector<vector<int>>& ps) {
        vector<tuple<int,int,int>> v;
        for(auto &e : rs) {
            v.push_back({e[0], e[1], INF});
            n = max(n, e[1]);
        }
        for (int i = 0; i < ps.size(); ++i) {
            v.push_back({ps[i][0], ps[i][1], i});
            n = max(n, ps[i][1]);
        }
        tr = vector<int>(n + 1);
        sort(v.begin(), v.end());
        vector<int> ans(ps.size());
        for (int i = v.size() - 1; i >= 0; --i) {
            auto [x, y, z] = v[i];
            if (z == INF) add(y);
            else ans[z] = query(n) - query(y - 1);
        }
        return ans;
    }
};

逆序对

数组中的逆序对

对于数组a, 如果存在下标 i < j, 且 a[i] > a[j]，则 a[i], a[j]是一个逆序对，求数组中逆序对总数。

方法1：归并排序

class Solution {
public:
    long long reversePairs(vector<int>& nums) {
        vector<int> tmp(nums.size());
        return mergeSort(0, nums.size() - 1, nums, tmp);
    }
private:
    long long mergeSort(int l, int r, vector<int>& nums, vector<int>& tmp) {
        if (l >= r) return 0;
        int m = (l + r) / 2;
        long long res = mergeSort(l, m, nums, tmp) + mergeSort(m + 1, r, nums, tmp);
        int i = l, j = m + 1;
        for (int k = l; k <= r; k++) tmp[k] = nums[k];
        for (int k = l; k <= r; k++) {
            if (i == m + 1) nums[k] = tmp[j++];
            else if (j == r + 1 || tmp[i] <= tmp[j]) nums[k] = tmp[i++];
            else {
                nums[k] = tmp[j++];
                res += m - i + 1; //如果是a[i] >= a[j]，tmp[i] <= tmp[j])改为tmp[i] < tmp[j])
            }
        }
        return res;
    }
};

方法二 树状数组+离散化

template<typename T>
struct fenwick {
    vector<T> a;
    int n;
    fenwick(int n): n(n), a(n) {}
    void add(int x, T v) {
        for(int i = x + 1; i <= n; i += i & -i) a[i - 1] += v;
    }
    T qry(int x) {
        T ret = 0;
        for(int i = min(x + 1, n); i > 0; i -= i & -i) ret += a[i - 1];
        return ret;
    }
};
template<typename T>
long long revpair(vector<T> a) {
    vector<T> b = a;
    sort(b.begin(), b.end());
    b.erase(unique(begin(b), end(b)), end(b));
    fenwick<int> fen(b.size());
    long long ret = 0;
    for(int i = 0; i < a.size(); ++i) {
        int p = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
        ret += i - fen.qry(p); //如果是a[i] >= a[j]，改为 i - fen.qry(p-1)
        fen.add(p, 1);
    }
    return ret;
}

区间并集

统计区间中的整数数目

leetcode 周赛293 T4

给你区间的 空集，请你设计并实现满足要求的数据结构：

  • 新增：添加一个区间到这个区间集合中。
  • 统计：计算出现在 至少一个 区间中的整数个数。

实现 CountIntervals 类：

  • CountIntervals() 使用区间的空集初始化对象
  • void add(int left, int right) 添加区间 [left, right] 到区间集合之中。
  • int count() 返回出现在 至少一个 区间中的整数个数。

注意：区间 [left, right] 表示满足 left <= x <= right 的所有整数 x 。

方法1:set

用一个 set 有序地维护所有不相交的区间，当加入区间 [left, right] 时，通过 lower_bound 快速找到第一个右端点大等于 left - 1 的区间，然后不断用接下来的区间和 [left, right] 合并，直到当前区间的左端点大于 right + 1。由于每个区间只会加入以及离开 set 一次，复杂度 O(nlogn)。

class CountIntervals {
    int ans;
    set<pair<int,int>> st;
public:
    CountIntervals(): ans(0){}
    
    void add(int left, int right) {
        int l = left, r = right;
        auto it = st.lower_bound({left - 1, -2e9});
        while (it != st.end() && it->second <= right + 1) {
            l = min(l, it->second);
            r = max(r, it->first);
            ans -= it->first - it->second + 1;
            st.erase(it++);
        }
        ans += r - l + 1;
        st.insert({r, l});
    }
    
    int count() {
        return ans;
    }
};

方法2:动态开点线段树

动态开点线段树： 通常来说，线段树占用空间是总区间长 n 的常数倍，空间复杂度是 O(n) 。然而，有时候 n 很巨大，而我们又不需要使用所有的节点，这时便可以动态开点——不再一次性建好树，而是一边修改、查询一边建立。我们不再用p2和p2+1代表左右儿子，而是用ls和rs记录左右儿子的编号。设总查询次数为 m ，则这样的总空间复杂度为 mlog(n) 。

对于本题来说，线段树的每个节点可以保存对应范围的左右端点 l 和 r，以及范围内 add 过的整数个数 sum。

代码实现时，无需记录 lazy tag，这是因为被覆盖的范围无需再次覆盖，因此若 sum 等于范围的长度 r-l+1，则可直接返回。

class CountIntervals {
    CountIntervals *left = nullptr, *right = nullptr;
    int l, r, sum = 0;
public:
    CountIntervals(): l(0), r(1e9){}
    CountIntervals(int l, int r): l(l), r(r){}
    
    void add(int L, int R) {
        if (sum == r - l + 1) return;
        if (L <= l && r <= R) {
            sum = r - l + 1;
            return;
        }
        int mid = (l + r) / 2;
        if (!left) left = new CountIntervals(l, mid);
        if (!right) right = new CountIntervals(mid + 1, r); // 动态开点
        if (L <= mid) left->add(L, R);
        if (mid < R) right->add(L, R);
        sum = left->sum + right->sum;
    }
    
    int count() {
        return sum;
    }
};

打赏一下

取消

感谢您的支持，我会继续努力的!

扫码支持
扫码支持
扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦