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

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代码

2021-04-22：给定很多线段，每个线段都有两个数[start, end]，表示线段开始位置和结束位置，左右都是闭区间，规定：1）线段的开始和结束位置一定都是整数值，2）线段重合区域的长度必须＞=的相关教程结束。