1. Check whether all characters have the same number of occurrences (hash count is omitted).

2. Minimum number of unoccupied chairs (Priority queue + simulation)

Use two priority queues, one sorted by seat number + departure time, and the other sorted by seat number, simulating in chronological order

type friend struct { arrive int leave int num int } type seat struct { freeTime int seatNum int } // Func (pq PriorityQueue) Len() int {return Len(pq)} // Bind the Less method, which uses the Less than sign, Func (pq PriorityQueue) Less(I, J int) bool {return pq[I]. FreeTime < pq[j]. FreeTime} func (pq PriorityQueue) swap (I, j int) {pq[I], Pq [j] = pq[j], pq[I]} Func (pq *PriorityQueue) Pop() interface{} {old := *pq n := len(old) item := old[n-1] *pq = old[0 : Func (pq *PriorityQueue) push (x interface{}) {item := x.(*seat) *pq = append(*pq, Item)} type IntHeap []int // define a type func (h IntHeap) Len() int {return Len(h IntHeap)} Less(I, j int) bool {return h[I]<h[j] return h[I]<h[j] Func (h IntHeap) Swap(I, j int) {// bind the Swap method, H [I], h[j] = h[j], h[I]} func (h *IntHeap) Pop() interface{} { N := len(old) x := old[n-1] *h = old[0: N -1] return x} func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int))} func smallestChair(times [][]int, targetFriend int) int {friends := make([]friend, len(times)) for i := 0 ; i < len(times) ; i++ { friends[i] = friend{arrive:times[i][0], leave:times[i][1], num:i} } sort.Slice(friends, func(i, j int) bool { if friends[i].arrive < friends[j].arrive { return true } return false }) cur := 0 needFree := make(PriorityQueue, 0) freeSeat := &IntHeap{} for i := 0 ; i < len(friends) ; i++ { if needFree.Len() ! = 0 && needFree[0].freeTime <= friends[i].arrive { for needFree.Len() > 0 && needFree[0].freeTime <= friends[i].arrive {  val, _ := heap.Pop(&needFree).(*seat) heap.Push(freeSeat, val.seatNum) } if friends[i].num == targetFriend { return (*freeSeat)[0] } heap.Push(&needFree, &seat{freeTime:friends[i].leave, seatNum:(*freeSeat)[0]}) heap.Pop(freeSeat) } else if freeSeat.Len() > 0 { if friends[i].num == targetFriend { return (*freeSeat)[0] } heap.Push(&needFree, &seat{freeTime:friends[i].leave, seatNum:(*freeSeat)[0]}) heap.Pop(freeSeat) } else { if friends[i].num == targetFriend { return cur } heap.Push(&needFree, &seat{friends[i].leave, cur}) cur++ } } return 0 }Copy the code

3. Describe the result of painting (difference)

Topic has been given color won’t be the same conditions, only need output color and at the same time, so we use difference array, put all the colors and statistics, since there is no the same color, so in a color join or leave, it must be a line segment can be output, need to use an array to record the endpoint, see the code.

func splitPainting(segments [][]int) [][]int64 { diff := make([]int, 100001) visited := make([]bool, 100001) res := make([][]int64, 0) for i := 0 ; i < len(segments) ; i++ { diff[segments[i][0]] += segments[i][2] diff[segments[i][1]] -= segments[i][2] visited[segments[i][0]] = true visited[segments[i][1]] = true } val := 0 start := 0 for i := 0 ; i < len(diff) ; i++ { if visited[i] { if val ! = 0 { t := make([]int64, 3) t[0] = int64(start) t[1] = int64(i) t[2] = int64(val) res = append(res, t) } start = i val += diff[i] } } return res }Copy the code

4. Number of people visible in queue (monotonic stack)

Num [I] = num[I] = num[I] = num[I] = num[I] If the current element is larger than the top of the stack, it is removed from the stack and counted. This value is the number of elements that can be seen by the current element. At the same time, the elements that have been removed from the stack have no effect on subsequent elements because they are smaller than the current element and will be blocked.

func canSeePersonsCount(heights []int) []int { res := make([]int, len(heights)) s := make([]int, 0) for i := len(heights) - 1; i >= 0 ; i-- { for len(s) > 0 && heights[i] > heights[s[len(s) - 1]] { res[i]++ s = s[:len(s) - 1] } if len(s) > 0 { res[i]++ } s  = append(s, i) } return res }Copy the code