华为 OD 机测试 - 间隔交织问题 - 贪婪算法（Python/JS/C/C++ 2024 年 E 卷 200 分） - IX、C++ 算法源代码

#include <bits/stdc++.h>
using namespace std;

// 定义线段结构体
struct Segment {
    int start;
    int end;
};

// 比较函数，用于排序
bool compareSegments(const Segment &a, const Segment &b) {
    if (a.start != b.start)
        return a.start < b.start;
    else
        return a.end > b.end;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n; // 读取线段数量
    vector<Segment> segments(n);
    for(int i=0;i<n;i++){
        char comma;
        cin >> segments[i].start >> comma >> segments[i].end;
        if(segments[i].start > segments[i].end){
            swap(segments[i].start, segments[i].end); // 确保起点小于等于终点
        }
    }
    
    // 按起点升序排序，如果起点相同，按终点降序排序
    sort(segments.begin(), segments.end(), compareSegments);
    
    int count = 0; // 最少线段数量
    int current_end = INT32_MIN; // 当前覆盖的右端点
    int i = 0;
    
    while(i < n){
        if(segments[i].start > current_end){
            // 找到所有起点 <= segments[i].start 的线段中终点最大的
            int max_end = segments[i].end;
            int j = i + 1;
            while(j < n && segments[j].start <= segments[i].start){
                if(segments[j].end > max_end){
                    max_end = segments[j].end;
                }
                j++;
            }
            count++;
            current_end = max_end;
            i = j;
        }
        else{
            // 找到所有起点 <= current_end 的线段中终点最大的
            int max_end = current_end;
            while(i < n && segments[i].start <= current_end){
                if(segments[i].end > max_end){
                    max_end = segments[i].end;
                }
                i++;
            }
            if(max_end > current_end){
                count++;
                current_end = max_end;
            }
            else{
                i++;
            }
        }
    }
    
    cout << count << "\n";
    return 0;
}

????下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）

????本文收录于，华为OD机试真题（Python/JS/C/C++）

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天****在线答疑。