algo-aha

轮廓线问题

• https://leetcode.com/problems/the-skyline-problem

vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
    // 扫描线算法，垂直线向右扫，遇到左端点把高度Hi加入集合，遇到右端点把Hi移出集合。
    // 若集合中最大高度变化（currHi!=prevHi），就得所需的跃变点。
    // 当x相同时，为避免currHi变化输出多余跃变点，左端点再按h从大到小排，右端点再按h从小到大排。
    // 不妨将左端点的高度取负值，然后统一排序。这样既区分了左右端点，又满足排序要求。
    vector<array<int,2>> points; // (x,h)
    for (auto &b : buildings) {
        points.push_back({b[0], -b[2]});
        points.push_back({b[1], b[2]});
    }
    sort(points.begin(), points.end());
    
    vector<vector<int>> ans;
    multiset<int> st;
    int prevHi = 0;
    for (auto& [x, h] : points) { // 遍历points相当于垂直线向右扫
        if (h < 0) st.insert(-h); // 左端点
        else st.erase(st.find(h)); // 右端点

        int currHi = st.empty() ? 0 : *st.rbegin();
        if (currHi != prevHi) {
            ans.push_back({ x, currHi });
            prevHi = currHi;
        }
    }
    return ans;
}

所有矩形的覆盖面积

• https://leetcode.com/problems/rectangle-area-ii/

int rectangleArea(vector<vector<int>>& rectangles) {
    // 扫描线算法：
    // 水平扫描线向上扫，每遇到y边界都累加一横块面积。
    // 面积高为 (y边界-前一y边界)，面积长为 旧区间集合的重叠长。

    // 要水平线向上扫，所以先按y坐标排序
    const int LOWER = 0, UPPER = 1;
    vector<vector<int>> events;
    for (auto &rect : rectangles) {
        events.push_back({rect[1], LOWER, rect[0], rect[2]});
        events.push_back({rect[3], UPPER, rect[0], rect[2]});
    }
    sort(events.begin(), events.end());

    // 遇到下边界把横坐标区间[x1,x2]加入集合，
    // 遇到上边界把[x1,x2]移出集合。
    const int MOD = 1e9 + 7;
    multiset<vector<int>> st; // st{ [x1,x2] }
    int preY = INT_MIN;
    int ans = 0;
    for (auto &e : events) {
        int y = e[0], type = e[1], x1 = e[2], x2 = e[3];
        if (preY != INT_MIN) {
            int height = y - preY;
            int width = getWidth(st);
            ans = (ans + (long)width * height) % MOD;
        }
        
        if (type == LOWER) st.insert({x1, x2});
        else st.erase(st.find({x1, x2}));
        preY = y;
    }
    return ans;
}

// 区间集合的重叠长
int getWidth(multiset<vector<int>> &st) {
    int ans = 0;
    int curr = INT_MIN;
    for (auto &x : st) {
        curr = max(curr, x[0]);
        ans += max(x[1] - curr, 0);
        curr = max(curr, x[1]);
    }
    return ans;
}

最多可参与的活动数

• https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/

int maxEvents(vector<vector<int>>& events) {
	const int N = events.size();
	// 事件按开始时间升序
	sort(events.begin(), events.end());
	// 尽量选结束时间早的，"进行中事件"的结束时间升序
	priority_queue<int, vector<int>, greater<>> pq;

	int maxDay = 0;
	for (auto& e : events) {
		maxDay = max(maxDay, e[1]);
	}
	int ans = 0;
	for (int day = 1, i = 0; day <= maxDay; day++) {  // 扫描线
		// 当天或之前开始的事件，结束时间入堆
		while (i < N && events[i][0] <= day) {
			pq.push(events[i][1]);
			i++;
		}
		// 移除已结束的事件
		while (!pq.empty() && pq.top() < day) {
			pq.pop();
		}

		// 取一个事件
		if (!pq.empty()) {
			pq.pop();
			ans++;
		}
	}
	return ans;
}