2023-07-20：假設(shè)一共有M個車庫，編號1 ~ M，時間點(diǎn)從早到晚是從1 ~ T，

一共有N個記錄，每一條記錄如下{a, b, c}，

表示一輛車在b時間點(diǎn)進(jìn)入a車庫，在c時間點(diǎn)從a車庫出去，

一共有K個查詢，每個查詢只有一個數(shù)字X，表示請問在X時刻，

有多少個車庫包含車的數(shù)量>=3，請返回K個查詢的答案。

1 <= M, N, K <= 10^5，

1 <= T <= 10^9。

大廠筆試面經(jīng)帖子。

答案2023-07-20：

算法1（getAns1）的大體過程如下：

1.遍歷所有記錄，找到最大時間點(diǎn) maxT。

2.將每個車庫和每個時間點(diǎn)的數(shù)量初始化為0。

3.遍歷記錄，對于每條記錄，獲取車庫編號 s、進(jìn)入時間 l、離開時間 r，將該時間段內(nèi)車庫 s 的數(shù)量加1。

4.遍歷查詢，對于每個查詢時間點(diǎn) t，統(tǒng)計(jì)數(shù)量大于等于3的車庫數(shù)目。

5.返回所有查詢的結(jié)果。

算法2（getAns2）的大體過程如下：

1.遍歷所有記錄和查詢，將時間點(diǎn)按照從小到大的順序存儲到數(shù)組 times 中，并記錄每個時間點(diǎn)的排名。

2.對于每條記錄，更新記錄的起始時間和結(jié)束時間為對應(yīng)的排名。

3.根據(jù)車庫編號對記錄進(jìn)行排序。

4.創(chuàng)建一個線段樹數(shù)據(jù)結(jié)構(gòu)，并初始化。

5.遍歷記錄，將統(tǒng)計(jì)數(shù)量大于等于3的時間段加入到線段樹中。

6.遍歷查詢，使用線段樹查詢對應(yīng)時間點(diǎn)的結(jié)果。

7.返回所有查詢的結(jié)果。

兩種算法實(shí)現(xiàn)的是相同的功能，但是基于不同的數(shù)據(jù)結(jié)構(gòu)和算法思路。算法1使用二維數(shù)組 stores 來統(tǒng)計(jì)每個車庫和時間點(diǎn)的數(shù)量，而算法2使用線段樹來高效地統(tǒng)計(jì)數(shù)量大于等于3的時間段。

算法1的總時間復(fù)雜度是O(n + m)，總空間復(fù)雜度是O(maxT * K + m)。

算法2的總時間復(fù)雜度是O((n + m) log(n + m) + n log n + maxT * log(maxT) + (n + m) log(maxT))，總空間復(fù)雜度是O(n + m + maxT)。

go完整代碼如下：

package?main

import?(
????"fmt"
????"math/rand"
????"sort"
????"time"
)

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

func?getAns1(m?int,?records?[][]int,?queries?[]int)?[]int?{
????maxT?:=?0
????for?_,?r?:=?range?records?{
????????maxT?=?getMax(maxT,?getMax(r[1],?r[2]))
????}
????for?_,?t?:=?range?queries?{
????????maxT?=?getMax(maxT,?t)
????}

????stores?:=?make([][]int,?m+1)
????for?i?:=?range?stores?{
????????stores[i]?=?make([]int,?maxT+1)
????}

????for?_,?record?:=?range?records?{
????????s?:=?record[0]
????????l?:=?record[1]
????????r?:=?record[2]?-?1
????????for?i?:=?l;?i?<=?r;?i++?{
????????????stores[s][i]++
????????}
????}

????k?:=?len(queries)
????ans?:=?make([]int,?k)
????for?i?:=?0;?i?<?k;?i++?{
????????curAns?:=?0
????????for?j?:=?1;?j?<=?m;?j++?{
????????????if?stores[j][queries[i]]?>=?3?{
????????????????curAns++
????????????}
????????}
????????ans[i]?=?curAns
????}

????return?ans
}

func?getAns2(m?int,?records?[][]int,?queries?[]int)?[]int?{
????n?:=?len(records)
????k?:=?len(queries)
????tn?:=?(n?<<?1)?+?k
????times?:=?make([]int,?tn+1)
????ti?:=?1
????for?_,?record?:=?range?records?{
????????times[ti]?=?record[1]
????????ti++
????????times[ti]?=?record[2]?-?1
????????ti++
????}
????for?_,?query?:=?range?queries?{
????????times[ti]?=?query
????????ti++
????}
????sort.Ints(times)
????for?_,?record?:=?range?records?{
????????record[1]?=?rank(times,?record[1])
????????record[2]?=?rank(times,?record[2]-1)
????}
????for?i?:=?0;?i?<?k;?i++?{
????????queries[i]?=?rank(times,?queries[i])
????}
????sort.Slice(records,?func(i,?j?int)?bool?{
????????return?records[i][0]?<?records[j][0]
????})
????st?:=?NewSegmentTree(tn)
????for?l?:=?0;?l?<?n;?{
????????r?:=?l
????????for?r?<?n?&&?records[l][0]?==?records[r][0]?{
????????????r++
????????}
????????countRange(records,?l,?r-1,?st)
????????l?=?r
????}
????ans?:=?make([]int,?k)
????for?i?:=?0;?i?<?k;?i++?{
????????ans[i]?=?st.query(queries[i])
????}
????return?ans
}

//?type?Record?struct?{
//??Garage?int
//??Start??int
//??End????int
//?}

type?SegmentTree?struct?{
????Tn???int
????Sum??[]int
????Lazy?[]int
}

func?NewSegmentTree(n?int)?*SegmentTree?{
????tn?:=?n
????sum?:=?make([]int,?(tn+1)<<2)
????lazy?:=?make([]int,?(tn+1)<<2)
????return?&SegmentTree{Tn:?tn,?Sum:?sum,?Lazy:?lazy}
}

func?(st?*SegmentTree)?pushUp(rt?int)?{
????st.Sum[rt]?=?st.Sum[rt<<1]?+?st.Sum[rt<<1|1]
}

func?(st?*SegmentTree)?pushDown(rt,?ln,?rn?int)?{
????if?st.Lazy[rt]?!=?0?{
????????st.Lazy[rt<<1]?+=?st.Lazy[rt]
????????st.Sum[rt<<1]?+=?st.Lazy[rt]?*?ln
????????st.Lazy[rt<<1|1]?+=?st.Lazy[rt]
????????st.Sum[rt<<1|1]?+=?st.Lazy[rt]?*?rn
????????st.Lazy[rt]?=?0
????}
}

func?(st?*SegmentTree)?add(l,?r?int)?{
????st.add0(l,?r,?1,?st.Tn,?1)
}

func?(st?*SegmentTree)?add0(L,?R,?l,?r,?rt?int)?{
????if?L?<=?l?&&?r?<=?R?{
????????st.Sum[rt]?+=?r?-?l?+?1
????????st.Lazy[rt]?+=?1
????????return
????}
????mid?:=?(l?+?r)?>>?1
????st.pushDown(rt,?mid-l+1,?r-mid)
????if?L?<=?mid?{
????????st.add0(L,?R,?l,?mid,?rt<<1)
????}
????if?R?>?mid?{
????????st.add0(L,?R,?mid+1,?r,?rt<<1|1)
????}
????st.pushUp(rt)
}

func?(st?*SegmentTree)?query(index?int)?int?{
????return?st.query0(index,?1,?st.Tn,?1)
}

func?(st?*SegmentTree)?query0(index,?l,?r,?rt?int)?int?{
????if?l?==?r?{
????????return?st.Sum[rt]
????}
????m?:=?(l?+?r)?>>?1
????st.pushDown(rt,?m-l+1,?r-m)
????if?index?<=?m?{
????????return?st.query0(index,?l,?m,?rt<<1)
????}?else?{
????????return?st.query0(index,?m+1,?r,?rt<<1|1)
????}
}

func?rank(sorted?[]int,?v?int)?int?{
????l?:=?1
????r?:=?len(sorted)
????ans?:=?0
????m?:=?0
????for?l?<=?r?{
????????m?=?(l?+?r)?/?2
????????//?fmt.Println(len(sorted),?l,?r,?m,?v)
????????if?sorted[m]?>=?v?{
????????????ans?=?m
????????????r?=?m?-?1
????????}?else?{
????????????l?=?m?+?1
????????}
????}
????return?ans
}

func?countRange(records?[][]int,?l,?r?int,?st?*SegmentTree)?{
????n?:=?r?-?l?+?1
????help?:=?make([][2]int,?n<<1)
????size?:=?0
????for?i?:=?l;?i?<=?r;?i++?{
????????if?records[i][1]?<=?records[i][2]?{
????????????help[size][0]?=?records[i][1]
????????????help[size][1]?=?1
????????????size++
????????????help[size][0]?=?records[i][2]
????????????help[size][1]?=?-1
????????????size++
????????}
????}
????sort.Slice(help[:size],?func(i,?j?int)?bool?{
????????if?help[i][0]?!=?help[j][0]?{
????????????return?help[i][0]?<?help[j][0]
????????}?else?{
????????????return?help[j][1]?<?help[i][1]
????????}
????})
????count?:=?0
????start?:=?-1
????for?i?:=?0;?i?<?size;?i++?{
????????point?:=?help[i][0]
????????status?:=?help[i][1]
????????if?status?==?1?{
????????????count++
????????????if?count?>=?3?{
????????????????if?start?==?-1?{
????????????????????start?=?point
????????????????}
????????????}
????????}?else?{
????????????if?start?!=?-1?&&?start?<=?point?{
????????????????st.add(start,?point)
????????????}
????????????count--
????????????if?count?>=?3?{
????????????????start?=?point?+?1
????????????}?else?{
????????????????start?=?-1
????????????}
????????}
????}
}

//?為了測試
func?randomRecords(n,?m,?t?int)?[][]int?{
????records?:=?make([][]int,?n)
????for?i?:=?0;?i?<?n;?i++?{
????????records[i]?=?make([]int,?3)
????}
????for?i?:=?0;?i?<?n;?i++?{
????????records[i][0]?=?rand.Intn(m)?+?1
????????a?:=?rand.Intn(t)?+?1
????????b?:=?rand.Intn(t)?+?1
????????records[i][1]?=?min(a,?b)
????????records[i][2]?=?max(a,?b)
????}
????return?records
}

//?為了測試
func?randomQueries(k,?t?int)?[]int?{
????queries?:=?make([]int,?k)
????for?i?:=?0;?i?<?k;?i++?{
????????queries[i]?=?rand.Intn(t)?+?1
????}
????return?queries
}

func?min(a,?b?int)?int?{
????if?a?<?b?{
????????return?a
????}
????return?b
}

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

func?same(ans1,?ans2?[]int)?bool?{
????if?len(ans1)?!=?len(ans2)?{
????????return?false
????}
????for?i?:=?0;?i?<?len(ans1);?i++?{
????????if?ans1[i]?!=?ans2[i]?{
????????????return?false
????????}
????}
????return?true
}

func?main()?{
????M?:=?20
????N?:=?300
????K?:=?500
????T?:=?5000
????testTimes?:=?5000
????fmt.Println("功能測試開始")
????rand.Seed(time.Now().UnixNano())
????for?i?:=?0;?i?<?testTimes;?i++?{
????????m?:=?rand.Intn(M)?+?1
????????n?:=?rand.Intn(N)?+?1
????????k?:=?rand.Intn(K)?+?1
????????t?:=?rand.Intn(T)?+?1
????????records?:=?randomRecords(n,?m,?t)
????????queries?:=?randomQueries(k,?t)
????????ans1?:=?getAns1(m,?records,?queries)
????????ans2?:=?getAns2(m,?records,?queries)
????????if?!same(ans1,?ans2)?{
????????????fmt.Println("出錯了!")
????????????return
????????}
????}
????fmt.Println("功能測試結(jié)束")

????fmt.Println("性能測試開始")
????m?:=?100000
????n?:=?100000
????k?:=?100000
????t?:=?1000000000
????records?:=?randomRecords(n,?m,?t)
????queries?:=?randomQueries(k,?t)
????fmt.Println("車庫規(guī)模?:?",?m)
????fmt.Println("記錄規(guī)模?:?",?n)
????fmt.Println("查詢條數(shù)?:?",?k)
????fmt.Println("時間范圍?:?",?t)
????start?:=?time.Now()
????getAns2(m,?records,?queries)
????end?:=?time.Now()
????fmt.Println("運(yùn)行時間?:?",?end.Sub(start).Milliseconds(),?"?毫秒")
????fmt.Println("性能測試結(jié)束")
}