LeetCode LCR 058. 我的日程安排表 I

Categories:

题目描述
思路分析
1. 解法一：有序区间 + 二分定位（推荐）
相似题目

题目描述

✅ LCR 058. 我的日程安排表 I

思路分析

解法一：有序区间 + 二分定位（推荐）

核心思路：

维护按起点升序的区间集合。

新区间只需与“前一个区间的结束”和“后一个区间的开始”比较即可判断是否重叠。

若不重叠则插入集合。

复杂度分析：

时间复杂度：O(n)，其中 n 表示已预约区间数，插入需要移动元素。

空间复杂度：O(n)，存储所有区间。

import java.util.*;

class MyCalendar {
    private final TreeMap<Integer, Integer> map = new TreeMap<>();

    public MyCalendar() {}

    public boolean book(int start, int end) {
        Integer floor = map.floorKey(start);
        if (floor != null && map.get(floor) > start) {
            return false;
        }

        Integer ceil = map.ceilingKey(start);
        if (ceil != null && ceil < end) {
            return false;
        }

        map.put(start, end);
        return true;
    }
}

import "sort"

type MyCalendar struct {
    intervals [][2]int
}

func Constructor() MyCalendar {
    return MyCalendar{}
}

func (c *MyCalendar) Book(start int, end int) bool {
    idx := sort.Search(len(c.intervals), func(i int) bool {
        return c.intervals[i][0] >= start
    })

    if idx > 0 && c.intervals[idx-1][1] > start {
        return false
    }

    if idx < len(c.intervals) && c.intervals[idx][0] < end {
        return false
    }

    c.intervals = append(c.intervals, [2]int{})
    copy(c.intervals[idx+1:], c.intervals[idx:])
    c.intervals[idx] = [2]int{start, end}
    return true
}

相似题目

题目	难度	考察点
56. 合并区间	中等	区间处理
57. 插入区间	中等	有序区间
435. 无重叠区间	中等	贪心
731. 我的日程安排表 II	中等	扫描线
732. 我的日程安排表 III	困难	扫描线

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/24056805