2021-04-22：给定很多线段，每个线段都有两个数[start, end]，表示线段开始位置和结束位置，左右都是

2021-04-22：给定很多线段，每个线段都有两个数[start, end]，表示线段开始位置和结束位置，左右都是闭区间，规定：1）线段的开始和结束位置一定都是整数值，2）线段重合区域的长度必须>=1。返回线段最多重合区域中，包含了几条线段 。

福大大 答案2021-04-22：

小根堆。
1.按线段起点排序。
2.遍历线段，push和pop小根堆。
2.1.小根堆循环pop小于等于线段起点的值。
2.2.把线段结束位置push到小根堆中。
2.3.收集最大的小根堆长度，假设是max。
3.返回max。

代码用golang编写。代码如下：

package main

import (
    "container/heap"
    "fmt"
    "sort"
)

func main() {
    lines := []*Line{
        &Line{Start: 1, End: 7},
        &Line{Start: 4, End: 8},
        &Line{Start: 2, End: 3},
        &Line{Start: 4, End: 9},
        &Line{Start: 4, End: 10}}
    ret := MaxCover(lines)
    fmt.Println(ret)
}

func MaxCover(lines []*Line) int {
    sort.Slice(lines, func(i int, j int) bool {
        return lines[i].Start < lines[j].Start
    })
    queue := IntHeap([]int{})
    max := 0
    for i := 0; i < len(lines); i++ {
        for queue.Len() > 0 {
            pop := queue.Pop().(int)
            if pop > lines[i].Start {
                heap.Push(&queue, pop) //由于heap里没有Peek方法，所以需要模拟Peek方法。
                break
            }
        }
        heap.Push(&queue, lines[i].End)
        max = getMax(max, queue.Len())
    }
    return max
}

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

type Line struct {
    Start int
    End   int
}

// An IntHeap is a min-heap of ints.
//type IntHeap []int
type IntHeap sort.IntSlice

//func (h IntHeap) Len() int           { return len(h) }
//func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
//func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h IntHeap) Len() int           { return sort.IntSlice(h).Len() }
func (h IntHeap) Less(i, j int) bool { return !sort.IntSlice(h).Less(i, j) }
func (h IntHeap) Swap(i, j int)      { sort.IntSlice(h).Swap(i, j) }

func (h *IntHeap) Push(x interface{}) {
    // Push and Pop use pointer receivers because they modify the slice's length,
    // not just its contents.
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

执行结果如下：

左神java代码