计算车流平均速度

在地里和leetcode面经版都看到这个题了，不知道能不能发到高频板块

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

大概写了下，不确定有没有漏掉edge case。

1. #!/usr/bin/python
   
2. # -*- coding: utf-8 -*-
   
3. 
   
4. import collections
   
5. 
   
6. def carstreamspeed(arr):
   
7.     nums = []
   
8.     for s, e, v in arr:
   
9.         nums.append([s, 1, v])
   
10.         nums.append([e, -1, v])
    
11. 
    
12.     nums.sort()
    
13.     cnt = 0
    
14.     cum_v = 0
    
15.     i = 0
    
16.     n = len(nums)
    
17.     res = []
    
18.     while i < n:
    
19.         j = i
    
20.         while j < n and nums[i][0] == nums[j][0]:
    
21.             if nums[j][1] == 1:
    
22.                 cum_v += nums[j][2]
    
23.                 cnt += 1
    
24.             else:
    
25.                 cum_v -= nums[j][2]
    
26.                 cnt -= 1
    
27.             j += 1
    
28.         if j == n:
    
29.             break
    
30.         tmp = [nums[i][0], nums[j][0], cum_v / float(cnt)]
    
31.         res.append(tmp)
    
32.         i = j
    
33.     return res
    
34. 
    
35. arr = [[0, 14, 90],
    
36.        [13, 15, 80],
    
37.        [13, 16, 70]]
    
38. 
    
39. print carstreamspeed(arr)
    
40. 
    
41. arr = [[0, 14, 90],
    
42.        [3, 15, 80]]
    
43. 
    
44. print carstreamspeed(arr)
    
45. 
    
46. arr = [[0, 14, 90],
    
47.        [13, 15, 80],
    
48.        [13, 16, 70],
    
49.        [15, 17, 100]]
    
50. 
    
51. print carstreamspeed(arr)
    
52. 
    
53. 
    

复制代码

应该是和meeting room2类似

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

dlwlrma 发表于 2019-5-25 07:28
大概写了下，不确定有没有漏掉edge case。
[mw_shl_code=python,true]#!/usr/bin/python
# -*- coding: u ...

思路就是扫描线， 然后从头到尾扫一遍，碰到起点，cum_v加上速度v, 碰到终点，cum_v减去v. O(nlogn)