generated from OpenDocCN/doc-template
-
Notifications
You must be signed in to change notification settings - Fork 0
/
0085.yaml
380 lines (380 loc) · 19.6 KB
/
0085.yaml
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
- en: Minimum Meeting Rooms Problem in SQL
id: totrans-0
prefs:
- PREF_H1
type: TYPE_NORMAL
zh: SQL 中的最小会议室问题
- en: 原文:[https://towardsdatascience.com/minimum-meeting-rooms-problem-in-sql-4d3a92365bdf?source=collection_archive---------18-----------------------#2023-01-05](https://towardsdatascience.com/minimum-meeting-rooms-problem-in-sql-4d3a92365bdf?source=collection_archive---------18-----------------------#2023-01-05)
id: totrans-1
prefs:
- PREF_BQ
type: TYPE_NORMAL
zh: 原文:[https://towardsdatascience.com/minimum-meeting-rooms-problem-in-sql-4d3a92365bdf?source=collection_archive---------18-----------------------#2023-01-05](https://towardsdatascience.com/minimum-meeting-rooms-problem-in-sql-4d3a92365bdf?source=collection_archive---------18-----------------------#2023-01-05)
- en: Compute (in SQL) the minimum number of meeting rooms needed to schedule a set
of meetings
id: totrans-2
prefs:
- PREF_H2
type: TYPE_NORMAL
zh: 计算(在 SQL 中)安排一组会议所需的最小会议室数量
- en: '[](https://medium.com/@dhruvbird?source=post_page-----4d3a92365bdf--------------------------------)[![Dhruv
Matani](../Images/d63bf7776c28a29c02b985b1f64abdd3.png)](https://medium.com/@dhruvbird?source=post_page-----4d3a92365bdf--------------------------------)[](https://towardsdatascience.com/?source=post_page-----4d3a92365bdf--------------------------------)[![Towards
Data Science](../Images/a6ff2676ffcc0c7aad8aaf1d79379785.png)](https://towardsdatascience.com/?source=post_page-----4d3a92365bdf--------------------------------)
[Dhruv Matani](https://medium.com/@dhruvbird?source=post_page-----4d3a92365bdf--------------------------------)'
id: totrans-3
prefs: []
type: TYPE_NORMAL
zh: '[](https://medium.com/@dhruvbird?source=post_page-----4d3a92365bdf--------------------------------)[![Dhruv
Matani](../Images/d63bf7776c28a29c02b985b1f64abdd3.png)](https://medium.com/@dhruvbird?source=post_page-----4d3a92365bdf--------------------------------)[](https://towardsdatascience.com/?source=post_page-----4d3a92365bdf--------------------------------)[![Towards
Data Science](../Images/a6ff2676ffcc0c7aad8aaf1d79379785.png)](https://towardsdatascience.com/?source=post_page-----4d3a92365bdf--------------------------------)
[Dhruv Matani](https://medium.com/@dhruvbird?source=post_page-----4d3a92365bdf--------------------------------)'
- en: ·
id: totrans-4
prefs: []
type: TYPE_NORMAL
zh: ·
- en: '[Follow](https://medium.com/m/signin?actionUrl=https%3A%2F%2Fmedium.com%2F_%2Fsubscribe%2Fuser%2F63f5d5495279&operation=register&redirect=https%3A%2F%2Ftowardsdatascience.com%2Fminimum-meeting-rooms-problem-in-sql-4d3a92365bdf&user=Dhruv+Matani&userId=63f5d5495279&source=post_page-63f5d5495279----4d3a92365bdf---------------------post_header-----------)
Published in [Towards Data Science](https://towardsdatascience.com/?source=post_page-----4d3a92365bdf--------------------------------)
·5 min read·Jan 5, 2023[](https://medium.com/m/signin?actionUrl=https%3A%2F%2Fmedium.com%2F_%2Fvote%2Ftowards-data-science%2F4d3a92365bdf&operation=register&redirect=https%3A%2F%2Ftowardsdatascience.com%2Fminimum-meeting-rooms-problem-in-sql-4d3a92365bdf&user=Dhruv+Matani&userId=63f5d5495279&source=-----4d3a92365bdf---------------------clap_footer-----------)'
id: totrans-5
prefs: []
type: TYPE_NORMAL
zh: '[关注](https://medium.com/m/signin?actionUrl=https%3A%2F%2Fmedium.com%2F_%2Fsubscribe%2Fuser%2F63f5d5495279&operation=register&redirect=https%3A%2F%2Ftowardsdatascience.com%2Fminimum-meeting-rooms-problem-in-sql-4d3a92365bdf&user=Dhruv+Matani&userId=63f5d5495279&source=post_page-63f5d5495279----4d3a92365bdf---------------------post_header-----------)
发表在 [Towards Data Science](https://towardsdatascience.com/?source=post_page-----4d3a92365bdf--------------------------------)
·5 分钟阅读·2023年1月5日[](https://medium.com/m/signin?actionUrl=https%3A%2F%2Fmedium.com%2F_%2Fvote%2Ftowards-data-science%2F4d3a92365bdf&operation=register&redirect=https%3A%2F%2Ftowardsdatascience.com%2Fminimum-meeting-rooms-problem-in-sql-4d3a92365bdf&user=Dhruv+Matani&userId=63f5d5495279&source=-----4d3a92365bdf---------------------clap_footer-----------)'
- en: --
id: totrans-6
prefs: []
type: TYPE_NORMAL
zh: --
- en: '[](https://medium.com/m/signin?actionUrl=https%3A%2F%2Fmedium.com%2F_%2Fbookmark%2Fp%2F4d3a92365bdf&operation=register&redirect=https%3A%2F%2Ftowardsdatascience.com%2Fminimum-meeting-rooms-problem-in-sql-4d3a92365bdf&source=-----4d3a92365bdf---------------------bookmark_footer-----------)![](../Images/ad9a445ea3172218a25498bf61789fa8.png)'
id: totrans-7
prefs: []
type: TYPE_NORMAL
zh: '[](https://medium.com/m/signin?actionUrl=https%3A%2F%2Fmedium.com%2F_%2Fbookmark%2Fp%2F4d3a92365bdf&operation=register&redirect=https%3A%2F%2Ftowardsdatascience.com%2Fminimum-meeting-rooms-problem-in-sql-4d3a92365bdf&source=-----4d3a92365bdf---------------------bookmark_footer-----------)![](../Images/ad9a445ea3172218a25498bf61789fa8.png)'
- en: Photo by [Dane Deaner](https://unsplash.com/@danedeaner?utm_source=medium&utm_medium=referral)
on [Unsplash](https://unsplash.com/?utm_source=medium&utm_medium=referral)
id: totrans-8
prefs: []
type: TYPE_NORMAL
zh: 图片由 [Dane Deaner](https://unsplash.com/@danedeaner?utm_source=medium&utm_medium=referral)
提供,来源于 [Unsplash](https://unsplash.com/?utm_source=medium&utm_medium=referral)
- en: The meeting room problem asks you to determine the least number of meeting rooms
needed to be able to schedule all the meetings from a given set such that there
are no conflicts. We shall see how to solve this in declarative SQL alone.
id: totrans-9
prefs: []
type: TYPE_NORMAL
zh: 会议室问题要求你确定安排所有会议所需的最少会议室数量,以便能够避免冲突。我们将探讨如何仅使用声明性 SQL 来解决这个问题。
- en: '**Previous Article**: [Validate Balanced Parenthesis using SQL](/validate-balanced-parenthesis-using-sql-5bb79732d772)'
id: totrans-10
prefs: []
type: TYPE_NORMAL
zh: '**上一篇文章**: [使用 SQL 验证平衡括号](/validate-balanced-parenthesis-using-sql-5bb79732d772)'
- en: Problem Statement
id: totrans-11
prefs:
- PREF_H1
type: TYPE_NORMAL
zh: 问题陈述
- en: Given a set of meeting start and end times (both inclusive), determine the least
number of meeting rooms needed to schedule all the meetings without any conflicts
(i.e. there should be no situation where a meeting room is not available for a
meeting, and neither should 2 meetings be scheduled at overlapping times in a
give meeting room).
id: totrans-12
prefs: []
type: TYPE_NORMAL
zh: 给定一组会议的开始和结束时间(均包括在内),确定安排所有会议所需的最少会议室数量,以避免任何冲突(即,会议室在会议进行时应始终可用,并且不能有两个会议在同一会议室内的时间重叠)。
- en: Online Coverage
id: totrans-13
prefs:
- PREF_H2
type: TYPE_NORMAL
zh: 在线讨论
- en: 'This problem is pretty popular in programming circles, and you can find coverage
here:'
id: totrans-14
prefs: []
type: TYPE_NORMAL
zh: 这个问题在编程圈子里相当流行,你可以在这里找到相关讨论:
- en: '[Geeksforgeeks](https://www.geeksforgeeks.org/minimum-halls-required-for-class-scheduling/)'
id: totrans-15
prefs:
- PREF_OL
type: TYPE_NORMAL
zh: '[Geeksforgeeks](https://www.geeksforgeeks.org/minimum-halls-required-for-class-scheduling/)'
- en: '[InterviewBit](https://www.interviewbit.com/problems/meeting-rooms/)'
id: totrans-16
prefs:
- PREF_OL
type: TYPE_NORMAL
zh: '[InterviewBit](https://www.interviewbit.com/problems/meeting-rooms/)'
- en: '[Javapoint](https://www.javatpoint.com/minimum-number-of-meeting-room-required-problem-in-java)'
id: totrans-17
prefs:
- PREF_OL
type: TYPE_NORMAL
zh: '[Javapoint](https://www.javatpoint.com/minimum-number-of-meeting-room-required-problem-in-java)'
- en: In fact, there are discussions about solving this problem in SQL too (this is
generally rare for the types of problems I’ve been covering in my articles).
id: totrans-18
prefs: []
type: TYPE_NORMAL
zh: 实际上,也有关于用 SQL 解决这个问题的讨论(这在我所覆盖的文章类型中通常较少见)。
- en: '[A Cool SQL Problem (And Why It Is Also a Bullshit SQL Problem)](https://ryxcommar.com/2019/06/24/a-cool-sql-problem-and-why-it-is-also-a-bullshit-sql-problem/)'
id: totrans-19
prefs:
- PREF_OL
type: TYPE_NORMAL
zh: '[一个很酷的 SQL 问题(以及它为何也是一个狗屎 SQL 问题)](https://ryxcommar.com/2019/06/24/a-cool-sql-problem-and-why-it-is-also-a-bullshit-sql-problem/)'
- en: '[(Stack Overflow) Minimum number of Meeting Rooms required to Accommodate all
Meetings in MySQL](https://stackoverflow.com/questions/48356312/minimum-number-of-meeting-rooms-required-to-accomodate-all-meetings-in-mysql)'
id: totrans-20
prefs:
- PREF_OL
type: TYPE_NORMAL
zh: '[(Stack Overflow) 在 MySQL 中容纳所有会议所需的最少会议室数量](https://stackoverflow.com/questions/48356312/minimum-number-of-meeting-rooms-required-to-accomodate-all-meetings-in-mysql)'
- en: Input Table Schema
id: totrans-21
prefs:
- PREF_H1
type: TYPE_NORMAL
zh: 输入表模式
- en: 'The input table looks like this:'
id: totrans-22
prefs: []
type: TYPE_NORMAL
zh: 输入表看起来像这样:
- en: '[PRE0]'
id: totrans-23
prefs: []
type: TYPE_PRE
zh: '[PRE0]'
- en: 'The columns have the following meaning:'
id: totrans-24
prefs: []
type: TYPE_NORMAL
zh: 这些列的含义如下:
- en: '**idx**: The index (unique ID) of this meeting'
id: totrans-25
prefs:
- PREF_OL
type: TYPE_NORMAL
zh: '**idx**:此会议的索引(唯一 ID)'
- en: '**start_at**: The timestamp at which this meeting starts'
id: totrans-26
prefs:
- PREF_OL
type: TYPE_NORMAL
zh: '**start_at**:会议开始时的时间戳'
- en: '**end_at**: The timestamp at which this meeting ends (the meeting is considered
to include this timestamp, so a meeting that begins at this timestamp can not
be scheduled in the same room as this meeting).'
id: totrans-27
prefs:
- PREF_OL
type: TYPE_NORMAL
zh: '**end_at**:会议结束时的时间戳(会议被视为包括此时间戳,因此在此时间戳开始的会议不能与该会议安排在同一房间)。'
- en: '[PRE1]'
id: totrans-28
prefs: []
type: TYPE_PRE
zh: '[PRE1]'
- en: '![](../Images/554a853f525a59f71856dfbad81fba5c.png)'
id: totrans-29
prefs: []
type: TYPE_IMG
zh: '![](../Images/554a853f525a59f71856dfbad81fba5c.png)'
- en: The input table for the provided data (Image by author)
id: totrans-30
prefs: []
type: TYPE_NORMAL
zh: 提供数据的输入表(作者提供的图片)
- en: 'First solution: O(n²)'
id: totrans-31
prefs:
- PREF_H1
type: TYPE_NORMAL
zh: 第一种解决方案:O(n²)
- en: This solution is discussed in both the online articles (links above) that talk
about solving this problem using SQL.
id: totrans-32
prefs: []
type: TYPE_NORMAL
zh: 这个解决方案在上述在线文章中讨论,这些文章讲述了如何使用 SQL 解决这个问题。
- en: The main idea is that one should look at every point in time (every second for
example) between the first and last timestamp at which meetings are scheduled
and check how many meetings overlap with that timestamp.
id: totrans-33
prefs: []
type: TYPE_NORMAL
zh: 主要思路是应该查看第一个和最后一个安排会议的时间戳之间的每一个时间点(例如每秒),并检查有多少会议与该时间点重叠。
- en: An optimization that can be performed is that instead of checking every point
in time, we only check the “interesting” points in time — i.e. the ones where
a meeting either begins or ends. This is because between any 2 such “interesting”
points, there will be no change in the number of scheduled meetings.
id: totrans-34
prefs: []
type: TYPE_NORMAL
zh: 可以进行的优化是,不必检查每个时间点,而只检查“有趣”的时间点——即会议开始或结束的时间点。这是因为在任何两个这样的“有趣”时间点之间,安排的会议数量不会发生变化。
- en: This solution has a runtime complexity of **O(n²)** since we need to join every
meeting **O(n)** and match it up with every unique time point **O(n)** that corresponds
to the start or end time point of a meeting.
id: totrans-35
prefs: []
type: TYPE_NORMAL
zh: 这个解决方案的时间复杂度是**O(n²)**,因为我们需要将每个会议**O(n)**与每个唯一的时间点**O(n)**(即会议的开始或结束时间点)匹配。
- en: '[PRE2]'
id: totrans-36
prefs: []
type: TYPE_PRE
zh: '[PRE2]'
- en: '![](../Images/48ff0fa86f9797e784b0c652bc06c363.png)'
id: totrans-37
prefs: []
type: TYPE_IMG
zh: '![](../Images/48ff0fa86f9797e784b0c652bc06c363.png)'
- en: The output from the first solution (Image by author)
id: totrans-38
prefs: []
type: TYPE_NORMAL
zh: 第一种解决方案的输出(作者提供的图片)
- en: Here, we can see that the minimum number of meeting rooms we need to schedule
all the meetings is 4\. This happens between time points 2022–01–05 and 2022–01–11.
id: totrans-39
prefs: []
type: TYPE_NORMAL
zh: 在这里,我们可以看到安排所有会议所需的最少会议室数量是4。这发生在时间点2022-01-05和2022-01-11之间。
- en: This is what the above output looks like graphically.
id: totrans-40
prefs: []
type: TYPE_NORMAL
zh: 上述输出的图形表示。
- en: '![](../Images/bd6c637fd63a4d5dbcbf05b438f99861.png)'
id: totrans-41
prefs: []
type: TYPE_IMG
zh: '![](../Images/bd6c637fd63a4d5dbcbf05b438f99861.png)'
- en: Graphical view of the output from the first solution (Image by author)
id: totrans-42
prefs: []
type: TYPE_NORMAL
zh: 第一种解决方案的输出图形视图(作者提供的图片)
- en: '**Estimated Cost:** The estimated cost for this query on a table of 6 rows
is [104k](https://explain.depesz.com/s/veps).'
id: totrans-43
prefs: []
type: TYPE_NORMAL
zh: '**预计成本:** 对于一个有6行的表格,这个查询的预计成本是[104k](https://explain.depesz.com/s/veps)。'
- en: 'Second solution: O(n log n)'
id: totrans-44
prefs:
- PREF_H1
type: TYPE_NORMAL
zh: 第二种解决方案:O(n log n)
- en: The main idea behind this solution is that once you have all the unique time
points at which meetings start and end, one can simply track how many “running”
meetings are present at those time points.
id: totrans-45
prefs: []
type: TYPE_NORMAL
zh: 该解决方案的主要思想是,一旦你有了所有会议开始和结束的唯一时间点,就可以简单地跟踪这些时间点上有多少个“进行中的”会议。
- en: '**Counter**: When a start time point is encountered, we need to increment a
single counter (running_sum), and when a meeting end time point is encountered,
we need to decrement this same counter.'
id: totrans-46
prefs: []
type: TYPE_NORMAL
zh: '**计数器:** 当遇到开始时间点时,我们需要递增一个计数器(running_sum),而当遇到会议结束时间点时,我们需要递减这个计数器。'
- en: '**Counting overlaps**: In case of meetings both starting and ending at a specific
time point, we need to be careful to first increment the counter and then decrement
it since the meeting is considered to be fully occupying its end time point. Hence,
we have code that says: *ORDER BY ts ASC,* ***delta DESC*** — i.e. if we don’t
order by delta descending, then we could process the end time point before the
start time point, and that would undercount the number of overlapping meetings.'
id: totrans-47
prefs: []
type: TYPE_NORMAL
zh: '**计数重叠:** 对于在特定时间点开始和结束的会议,我们需要注意首先递增计数器,然后再递减,因为会议被认为完全占用其结束时间点。因此,我们有这样的代码:*ORDER
BY ts ASC,* ***delta DESC*** — 即如果我们不按delta降序排序,那么可能会在开始时间点之前处理结束时间点,这会导致重叠会议数量的低估。'
- en: The runtime complexity of this solution is **O(n log n)** since it’s dominated
by the cost of ordering all the unique time points in non-decreasing order of
timestamp.
id: totrans-48
prefs: []
type: TYPE_NORMAL
zh: 该解决方案的运行时复杂度是**O(n log n)**,因为它由对所有唯一时间点按时间戳的非递减顺序排序的成本主导。
- en: '[PRE3]'
id: totrans-49
prefs: []
type: TYPE_PRE
zh: '[PRE3]'
- en: '![](../Images/3fb7fb79a427360d93bb18b1362b7903.png)'
id: totrans-50
prefs: []
type: TYPE_IMG
zh: '![](../Images/3fb7fb79a427360d93bb18b1362b7903.png)'
- en: The output from the second solution (Image by author)
id: totrans-51
prefs: []
type: TYPE_NORMAL
zh: 第二种解决方案的输出(作者提供的图片)
- en: We can see that the minimum number of meeting rooms (4) needed to schedule all
meetings without conflict is between 2022–01–05 and 2022–01–11 (same as the solution
above).
id: totrans-52
prefs: []
type: TYPE_NORMAL
zh: 我们可以看到,安排所有会议而不发生冲突所需的最小会议室数量(4)在2022年1月5日至2022年1月11日之间(与上面的解决方案相同)。
- en: This is what the output above looks like graphically.
id: totrans-53
prefs: []
type: TYPE_NORMAL
zh: 上述输出的图形表示。
- en: '![](../Images/9d9b355f59a87227f86ad607c7e4493f.png)'
id: totrans-54
prefs: []
type: TYPE_IMG
zh: '![](../Images/9d9b355f59a87227f86ad607c7e4493f.png)'
- en: Graphical view of the output from the second solution (Image by author)
id: totrans-55
prefs: []
type: TYPE_NORMAL
zh: 第二种解决方案的输出图形视图(作者提供的图片)
- en: '**Estimated Cost:** The estimated cost for this query on a table of 6 rows
is [474](https://explain.depesz.com/s/2OVR).'
id: totrans-56
prefs: []
type: TYPE_NORMAL
zh: '**预计成本:** 对于一个有6行的表格,这个查询的预计成本是[474](https://explain.depesz.com/s/2OVR)。'
- en: SQL Fiddle
id: totrans-57
prefs:
- PREF_H1
type: TYPE_NORMAL
zh: SQL Fiddle
- en: The SQL Fiddle link to all the solutions in this post can be found [here](http://sqlfiddle.com/#!17/75a65/7).
id: totrans-58
prefs: []
type: TYPE_NORMAL
zh: 本文中所有解决方案的SQL Fiddle链接可以在[这里](http://sqlfiddle.com/#!17/75a65/7)找到。
- en: Conclusion
id: totrans-59
prefs:
- PREF_H1
type: TYPE_NORMAL
zh: 结论
- en: This problem has some similarities with the previous problem we saw ([Validate
Balanced Parenthesis using SQL](/validate-balanced-parenthesis-using-sql-5bb79732d772))
in so far as the use of the running sum using SQL window functions is concerned.
id: totrans-60
prefs: []
type: TYPE_NORMAL
zh: 这个问题与我们之前看到的[使用SQL验证平衡括号](/validate-balanced-parenthesis-using-sql-5bb79732d772)有些相似,主要体现在使用SQL窗口函数的运行总和。
- en: We saw how we can use SQL window functions (yet again) to see how one can leverage
a simple concept such as a running sum to solve seemingly complex problems.
id: totrans-61
prefs: []
type: TYPE_NORMAL
zh: 我们看到如何使用SQL窗口函数(再次)来利用一个简单的概念如运行总和来解决看似复杂的问题。