笔试时间：2024年09月23日 秋招

历史笔试传送门：2023秋招笔试合集

第一题

题目

给定一组区间(eg:[10,20].[3050].[40,80])，请设计程序来合并所有重叠的区间，并保证合并后的区间按升序排序。示例:

给定区间组:[10,20].[30,50].[40,80]

合并后结果:[10,20].[30,80]问题:请补全下面程序的【】处，以实现该功能。注意:答题后请勿将【】框别

参考题解

先对所有区间按起始位置升序排序将第一个区间添加到结果集中遍历区间列表，从第二个开始3.1 如果当前区间和结果集最后一个区间没有重叠，直接加入结果集3.2 如果有重叠，更新结果集最后一个区间的结束位置。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <algorithm>

class Interval {
public:
    int start;
    int end;

    Interval(int s, int e) : start(s), end(e) {}

    friend std::ostream& operator<<(std::ostream& os, const Interval& interval) {
        return os << "[" << interval.start << ", " << interval.end << "]";
    }
};

std::vector<Interval> merge(std::vector<Interval>& intervals) {
    std::vector<Interval> res;
    if (intervals.empty()) {
        return res;
    }

    // Sort intervals based on start time
    std::sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) {
        return a.start < b.start;
    });

    res.push_back(intervals[0]);

    for (size_t i = 1; i < intervals.size(); i++) {
        Interval& next = intervals[i];
        Interval& origin = res.back();

        if (next.start > origin.end) {
            res.push_back(next);
        } else {
            origin.end = std::max(origin.end, next.end);
        }
    }

    return res;
}

int main() {
    std::vector<Interval> intervals = { Interval(10, 20), Interval(30, 50) };
    // 可以继续添加其他区间

    std::vector<Interval> mergedIntervals = merge(intervals);
    for (const Interval& interval : mergedIntervals) {
        std::cout << interval << " ";
    }
    std::cout << std::endl;

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Overlay {
    public static void main(String[] args) {
        List<Interval> intervals = new ArrayList<>();
        intervals.add(new Interval(10, 20));
        intervals.add(new Interval(30, 50));
       
        // ... 可以继续添加其他区间

        System.out.println(merge(intervals));
    }

 
    public static List<Interval> merge(List<Interval> intervals) {
        List<Interval> res = new ArrayList<>();
        // 去除特殊情况
        if (intervals.size() == 0) {
            return res;
        }

        // 先对所有区间按起始位置升序排序
        Collections.sort(intervals, (Interval o1, Interval o2) -> {
            return o1.start - o2.start;
        });

        // 将第一个区间添加到结果集中
        res.add(intervals.get(0));
        int count=0;

        // 3. 遍历区间列表，从第二个开始
        for (int i = 1; i < intervals.size(); i++) {
            Interval next = intervals.get(i);
            Interval origin = res.get(count);
            // 3.1 如果当前区间和结果集最后一个区间没有重叠，直接加入结果集
            if (next.start > origin.end) {
                res.add(next);
            } else {
                // 区间有重叠，更新结尾
                next.end = Math.max(next.end, origin.end);  
                Interval newInterval = new Interval(origin.start, next.end);  
    
                
                if (next.end < origin.end) {
                    next.end = origin.end;  // 【5】确保next.end等于origin.end的较大值
                }
    
                res.add(newInterval);  // 将新的合并区间加入结果集
            }
        }

        return res;
    }

    // 区间类
    static class Interval {
        int start;
        int end;

        public Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public String toString() {
            return "[" + start + ", " + end + "]";
        }
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

class Interval:
    def __init__(self, start, end):
        self.start = start
        self.end = end

    def __repr__(self):
        return f"[{self.start}, {self.end}]"


def merge(intervals):
    res = []
    if not intervals:
        return res

    # Sort intervals based on start time
    intervals.sort(key=lambda x: x.start)

    res.append(