朴素算法Bare Algo

排序与区间

排序、区间合并/插入、扫描线、会议室与重叠区间等经典题型。

算法题

(8)
56. 合并区间
中等
以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi]。请你合并所有重叠的区间,并返回一个不重叠的区间数组。
数组排序
57. 插入区间
中等
给你一个无重叠的,按照区间起始端点排序的区间列表。在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠。
数组
253. 会议室 II
中等
给你一个会议时间安排的数组 intervals,每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi],返回所需会议室的最小数量。
数组双指针排序堆
3454. 分割正方形 II
困难
给你一个二维整数数组 squares,找到一个最小的 y 坐标,对应一条水平线,使得该线以上正方形的总面积等于该线以下正方形的总面积。
扫描线线段树二分查找
218. 天际线问题
困难
城市的 天际线 是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度,请返回天际线。
数组分治堆线段树
729. 我的日程安排表 I
中等
实现一个 MyCalendar 类来存放你的日程安排。如果要添加的日程安排不会造成重复预订,则可以存储这个新的日程安排。
设计线段树二分查找
1235. 规划兼职工作
困难
你打算利用空闲时间来做兼职工作赚些零花钱。这里有 n 份兼职工作,每份工作预计从 startTime[i] 开始到 endTime[i] 结束,报酬为 profit[i]。
数组二分查找动态规划排序
2943. 最大化网格图中正方形空洞的面积
中等
给你一个网格图,由横线段 and 竖线段组成。你可以移除部分线段,返回移除后剩余网格图中最大正方形空洞的面积。
数组排序贪心

实际应用

(5)
日程冲突检测
中等
在日历应用中检测多个事件是否存在时间重叠,使用区间合并或扫描线算法实现 O(N log N) 的冲突检测。
区间合并扫描线日历应用区间处理
视频时间轴合并
简单
视频编辑器中合并多段选区,或音视频处理中合并静音/高亮片段,使用区间合并保证结果不重叠。
多媒体处理编辑器
资源调度/会议室分配
困难
根据任务时间段分配最少的资源(如计算节点、会议室),使用扫描线或贪心算法求最大并发数。
扫描线堆调度系统资源管理
重叠区域面积计算
困难
在地图/CAD应用中计算多个矩形区域的并集面积,使用扫描线+线段树实现 O(N log N) 的精确计算。
扫描线线段树几何计算
带宽/时间槽分配
中等
在网络或广播系统中,将有限的时间槽分配给多个请求,判断是否可行并找出最优分配方案。
区间调度网络协议资源分配