算法

差分思想的应用

Posted by Liao on 2023-03-02

LC253. 会议室 II

给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，返回 所需会议室的最小数量 。

示例 1：

1
2
输入：intervals = [[0,30],[5,10],[15,20]]
输出：2

示例 2：

1
2
输入：intervals = [[7,10],[2,4]]
输出：1

提示：

  • 1 <= intervals.length <= 104
  • 0 <= starti < endi <= 106
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func minMeetingRooms(intervals [][]int) int {
	var timestamp [][]int
  // 1、预处理
	for _, v := range intervals {
		timestamp = append(timestamp, []int{v[0], 1})
		timestamp = append(timestamp, []int{v[1], -1})
	}
  
	// 2、从小到大排序
	var less func(i, j int) bool
	less = func(i, j int) bool {
		if timestamp[i][0] == timestamp[j][0] {
			return timestamp[i][1] <= timestamp[j][1]
		}
		return timestamp[i][0] <= timestamp[j][0]
	}
	sort.Slice(timestamp, less)

  // 3、汇总
	cur := 0
	ans := 0
	for _, v := range timestamp {
		cur += v[1]
		ans = max(ans, cur)
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

LC1094 拼车

车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）

给定整数 capacity 和一个数组 trips , trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。

当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。

示例 1：

1
2
输入：trips = [[2,1,5],[3,3,7]], capacity = 4
输出：false

示例 2：

1
2
输入：trips = [[2,1,5],[3,3,7]], capacity = 5
输出：true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func carPooling(trips [][]int, capacity int) bool {
	capLoad := make([]int, 1001)
	for _, v := range trips {
		capLoad[v[1]] -= v[0]
		capLoad[v[2]] += v[0]
	}
  
	for i := range capLoad {
		capacity += capLoad[i]
		if capacity < 0 {
			return false
		}
	}
	return true
}

LC759. 员工空闲时间

给定员工的 schedule 列表，表示每个员工的工作时间。

每个员工都有一个非重叠的时间段 Intervals 列表，这些时间段已经排好序。

返回表示 所有 员工的 共同，正数长度的空闲时间 的有限时间段的列表，同样需要排好序。

示例 1：

1
2
3
4
5
6
输入：schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
输出：[[3,4]]
解释：
共有 3 个员工，并且所有共同的
空间时间段是 [-inf, 1], [3, 4], [10, inf]。
我们去除所有包含 inf 的时间段，因为它们不是有限的时间段。

示例 2：

1
2
输入：schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
输出：[[5,6],[7,9]]

（尽管我们用 [x, y] 的形式表示 Intervals ，内部的对象是 Intervals 而不是列表或数组。例如，schedule[0][0].start = 1, schedule[0][0].end = 2，并且 schedule[0][0][0] 是未定义的）

而且，答案中不包含 [5, 5] ，因为长度为 0。

注：

  1. schedule 和 schedule[i] 为长度范围在 [1, 50]的列表。
  2. 0 <= schedule[i].start < schedule[i].end <= 10^8。

注：输入类型于 2019 年 4 月 15 日 改变。请重置为默认代码的定义以获取新方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package main

import (
	"fmt"
	"sort"
)

type Interval struct {
	Start int
	End   int
}

func main() {
	var schedule [][]*Interval
	schedule = [][]*Interval{
		{{1, 2}, {5, 6}, {1, 3}, {4, 10}},
	}
	ans := employeeFreeTime(schedule)
	fmt.Println(ans)
}

func employeeFreeTime(schedule [][]*Interval) []*Interval {
	var arr [][]int
  // 1、预处理差分数组
	for _, mytime := range schedule {
		for j := range mytime {
			arr = append(arr, []int{mytime[j].Start, 0})
			arr = append(arr, []int{mytime[j].End, 1})
		}
	}

  // 2、从小到大排序
	var less func(i, j int) bool
	less = func(i, j int) bool {
		if arr[i][0] == arr[j][0] {
			return arr[i][1] <= arr[j][1]
		}
		return arr[i][0] <= arr[j][0]
	}
	sort.Slice(arr, less)

  // 3、汇总
	pre, cur := -1, 0
	ans := make([]*Interval, 0)
	for _, v := range arr {
		if pre >= 0 && cur == 0 {
			ans = append(ans, &Interval{pre, v[0]})
		}
		if v[1] == 0 {
			cur += 1
		} else {
			cur -= 1
		}
		pre = v[0]
	}
	return ans
}

FEATURED TAGS
算法
FRIENDS