讨论/面试考题/计算重叠时间区间的百分比(腾讯笔试题)/
计算重叠时间区间的百分比(腾讯笔试题)

描述
程序中有⼀个数据库,会被多线程访问。为了确认这个数据库被并发访问的⼏率,在程序中加
入了统计代码,记录下每个线程每次访问数据库的开始和结束时间。最终得到CSV格式的⽂
件,如下所⽰:
ThreadId, BeginTime, EndTime
1, 10, 20
2, 15, 30
3, 40, 60
3, 90, 95
1, 50, 80
2, 70, 100
1, 105, 115
以上数据表明,线程1在 [10,20] 、 [50,80] 和 [105,115] 这三个时间区间访问了数据库;线
程2在 [15,30] 和 [70,100] 这两个时间区间访问了数据库;线程3在 [40,60] 和 90,95 这两个
时间区间访问了数据库。
可⻅,每个线程访问数据库的时间区间有重叠。现在你的⼯作是,计算出有重叠的时间区间占
总时间区间的百分比。
以上⾯的数据为例,访问数据库的总时间区间为:
[10,30] 、 [40,100] 、 [105,115]
总时⻓为:
(30 - 10) + (100 - 40) + (115 - 105) = 90
有重叠的时间区间为:
[15,20] 、 [50,60] 、 [70,80] 、 [90,95]
总时⻓为:
(20 - 15) + (60 - 50) + (80 - 70) + (95 - 90) = 30
百分比为:
30 / 90 = 0.33
要求

  1. 实现⼀个命令⾏程序。
  2. 所有数据保存在⼀个 .csv ⽂件中,⽂件的路径通过程序启动参数传入。
  3. 计算结果输出到标准输出。
  4. 注意BeginTime和EndTime是真实的 std::time_t 时间值。
  5. 已有⼀个⼯具函数可使⽤:
    std::vectorstd::string SplitByComma(const std::string& line);
    该函数以逗号作为分隔符,把传入的字符串切割成字符串列表,同时会把字符串前后的空格都
    去掉。
  6. 可以使⽤你熟悉的语⾔来写。如果不使⽤C++,需要把 SplitByComma 的声明重新写⼀遍。
展开讨论
共 2 个讨论

附上golang实现的代码,供大家查看

//区间合并问题的改版
func overlapTime(arr [][]int) float64 {
	//1、对arr进行排序
	sort.Slice(arr, func(i, j int) bool {
		return arr[i][0] < arr[j][0]
	})
	//2、将区间进行合并,合并发同时计算重叠时间的区间
	queue := make([][]int, 0)
	queue = append(queue, arr[0])
	//定义重叠时间
	overlaptime := 0
	for i := 1; i < len(arr); i++ {
		if arr[i][0] <= queue[len(queue)-1][1] {
			//更新重叠时间
			overlaptime += int(math.Min(float64(queue[len(queue)-1][1]), float64(arr[i][1]))) - arr[i][0]
			//更新重叠区间
			queue[len(queue)-1][1] = int(math.Max(float64(queue[len(queue)-1][1]), float64(arr[i][1])))
		} else {
			queue = append(queue, arr[i])
		}
	}
	//计算总时间
	totaltime := 0
	for i := 0; i < len(queue); i++ {
		totaltime += (queue[i][1] - queue[i][0])
	}
	return float64(overlaptime) / float64(totaltime)
}

func main() {
	arr := [][]int{{10, 20}, {15, 30}, {40, 60}, {90, 95}, {50, 80}, {70, 100}, {105, 115}}
	res := overlapTime(arr)
	fmt.Println(res)
}

56题,合并区间。 改改就能用。算法思路差不多。排序,合并左右交叉部分,计算交叉部分。