2023华为OD机试真题【区间交叠/贪心算法】【Python Java C++】

布满荆棘的人生 2023-09-27 17:35 67阅读 0赞

### 题目描述 ###

> 给定坐标轴上的一组线段，线段的起点和终点均为整数并且长度不小于1，请你从中找到最少数量的线段，这些线段可以覆盖住所有线段。
> 
> **输入描述**  
> 第一行输入为所有线段的数量，不超过10000，后面每行表示一条线段，格式为”x,y”，  
> x和y 分别表示起点和终点，取值范围是\[-10^5 ，10^5\]。  
> **输出描述**
> 
> 最少线段数量，为正整数。  
> **输入**  
> 3  
> 1,4  
> 2,5  
> 3,6  
> **输出**  
> 2

### 题意解读 ###

首先，用示例来**理解题意**：现在有三条线段：

一号线段：起点1，终点4；

二号线段：起点2，终点5；

三号线段：起点3，终点6；

![在这里插入图片描述][d436367268f64b8b8cfa5b81f82865b0.png]  
我们要从这三条线段中，选出若干条线段，覆盖`1~6`整个区间。

比如，我们可以选择 一号、二号、三号。一号覆盖 `1~4` ，二号覆盖 `2~5`，三号覆盖`3~6`，三条线段加起来可以覆盖`1~6`整个区间。但是，题目要求**尽可能选择少的线段**。因此，我们只用选择一号、三号，也能覆盖`1~6`整个区间。所以，答案就是选择`2`条线段（即一号、三号）。

### 解题思路 ###

这是一道典型的**贪心算法**，贪心策略如下：

首先，将所有线段按起点**从小到大**排序。

然后遍历排序后的线段，每遍历到一个线段（我们称当前正在遍历的线段为`current`线段），找出后面的线段中左端点小于等于`current`线段的右端点的**所有线段**（我们称之为**备选线段**），找出**备选线段**中右端点最大的一个线段`maxLine`。下一步遍历`maxLine`。

不断重复以上操作，直到覆盖完整个长度为m的区间，就能得到最少的线段数。

### 视频讲解 ###

2023华为机试真题【区间交叠/贪心算法】

### 示例代码（Java版本） ###

import java.util.LinkedList;
    import java.util.Arrays;
    import java.util.Scanner;
    
    public class Main {
        
    
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            
            int n = sc.nextInt();
            sc.nextLine();
            
            Integer[][] segs = new Integer[n][];
            for (int i = 0; i < n; i++) {
        
                segs[i] = getSeg(sc.nextLine());
            }
            
            sort(segs);
    
            LinkedList<Integer[]> coverSegs = cover(segs);
    
            System.out.println(coverSegs.size());
        }
    
        private static Integer[] getSeg(String line) {
        
            String[] parts = line.split(",");
            return new Integer[]{
        Integer.parseInt(parts[0]), Integer.parseInt(parts[1])};
        }
    
        private static void sort(Integer[][] segs) {
        
            Arrays.sort(segs, (a, b) -> a[0].compareTo(b[0]));
        }
    
        private static LinkedList<Integer[]> cover(Integer[][] segs) {
        
            LinkedList<Integer[]> stack = new LinkedList<>();
            stack.add(segs[0]);
    
            for (int i = 1; i < segs.length; i++) {
        
                while (true) {
        
                    if (stack.isEmpty()) {
        
                        stack.add(segs[i]);
                        break;
                    }
                    
                    Integer[] top = stack.getLast();
                    Integer[] cur = segs[i];
    
                    if (cur[0] <= top[0]) {
        
                        if (cur[1] <= top[0]) {
        
                            break;
                        } else if (cur[1] < top[1]) {
        
                            break;
                        } else {
        
                            stack.removeLast();
                        }
                    } else if (cur[0] < top[1]) {
        
                        if (cur[1] <= top[1]) {
        
                            break;
                        } else {
        
                            stack.add(new Integer[]{
        top[1], cur[1]});
                            break;
                        }
                    } else {
        
                        stack.add(cur);
                        break;
                    }
                }
            }
    
            return stack;
        }
    }

### 示例代码（Python版本） ###

def get_segs(line):
        parts = line.split(",")
        return [int(parts[0]), int(parts[1])]
    
    def sort_segs(segs):
        return sorted(segs, key=lambda x: x[0])
    
    def cover(segs):
        stack = [segs[0]]
    
        for i in range(1, len(segs)):
            while True:
                if not stack:
                    stack.append(segs[i])
                    break
    
                top = stack[-1]
                cur = segs[i]
    
                if cur[0] <= top[0]:
                    if cur[1] <= top[0]:
                        break
                    elif cur[1] < top[1]:
                        break
                    else:
                        stack.pop()
                elif cur[0] < top[1]:
                    if cur[1] <= top[1]:
                        break
                    else:
                        stack.append([top[1], cur[1]])
                        break
                else:
                    stack.append(cur)
                    break
    
        return stack
    
    if __name__ == '__main__':
        n = int(input())
        segs = [get_segs(input()) for _ in range(n)]
        sorted_segs = sort_segs(segs)
        cover_segs = cover(sorted_segs)
    
        print(len(cover_segs))

### 示例代码（C++） ###

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <string>
    #include <sstream>
    
    using namespace std;
    
    // 将字符串形式的线段转换为vector
    vector<int> getSegments(const string& line) {
        
        vector<int> segs;
        istringstream iss(line);
        string x, y;
        getline(iss, x, ',');
        getline(iss, y);
        segs.push_back(atoi(x.c_str()));
        segs.push_back(atoi(y.c_str()));
        return segs;
    }
    
    // 对线段按照起点进行排序
    bool compareSegments(const vector<int>& a, const vector<int>& b) {
        
        return a[0] < b[0];
    }
    
    // 找到可以覆盖所有线段的最少线段数量
    vector<vector<int>> findCover(vector<vector<int>>& segs) {
        
        vector<vector<int>> stack;
        stack.push_back(segs[0]);
        for (size_t i = 1; i < segs.size(); ++i) {
        
            while (true) {
        
                if (stack.empty()) {
        
                    stack.push_back(segs[i]);
                    break;
                }
    
                vector<int>& top = stack.back();
                vector<int>& cur = segs[i];
    
                if (cur[0] <= top[0]) {
        
                    if (cur[1] <= top[0]) break;
                    else if (cur[1] < top[1]) break;
                    else stack.pop_back();
                }
                else if (cur[0] < top[1]) {
        
                    if (cur[1] <= top[1]) break;
                    else {
        
                        stack.push_back(vector<int>{
        top[1], cur[1]});
                        break;
                    }
                }
                else {
        
                    stack.push_back(cur);
                    break;
                }
            }
        }
        return stack;
    }
    
    int main() {
        
        int n;
        cin >> n;
        string input;
        getline(cin, input); 
    
        vector<vector<int>> segs;
        for (int i = 0; i < n; ++i) {
        
            getline(cin, input);
            segs.push_back(getSegments(input));
        }
    
        // 对线段进行排序
        sort(segs.begin(), segs.end(), compareSegments);
    
        // 可以覆盖所有线段的最少线段集合
        vector<vector<int>> coverSegs = findCover(segs);
    
        // 最少线段数量
        cout << coverSegs.size() << endl;
    
        return 0;
    }

[d436367268f64b8b8cfa5b81f82865b0.png]: https://img-blog.csdnimg.cn/d436367268f64b8b8cfa5b81f82865b0.png