区间合并

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    var reader = bufio.NewReader(os.Stdin)
    var xx = readInt(reader)
    if xx <= 1 {
        fmt.Println(xx)
        return
    }
    var a = make([][]int, xx)
    for i := 0; i < xx; i++ {
        a[i] = readArray(reader, " ")
    }

    var cnt = 1
    // 1.按左端点排序
    //quickSort(a, 0, xx-1)    // 快速排序有问题
    a = mergeSort(a)
    //fmt.Println(a)

    // 2.扫描，将存在交集的区间合并（如果不存在交集，则区间个数累计+1）
    var y = a[0][1]
    for i := 1; i < xx; i++ {
        if a[i][0] > y {
            cnt += 1
            y = a[i][1]
        } else if a[i][1] > y {
            y = a[i][1]
        }
    }

    fmt.Println(cnt)
}

func mergeSort(a [][]int) [][]int {
    if len(a) <= 1 {
        return a
    }
    return merge(mergeSort(a[:len(a)>>1]), mergeSort(a[(len(a)>>1):]))
}

func merge(a, b [][]int) [][]int {
    var (
        i   int
        j   int
        ans [][]int
    )

    for i < len(a) && j < len(b) {
        if a[i][0] <= b[j][0] {
            ans = append(ans, a[i])
            i++
        } else {
            ans = append(ans, b[j])
            j++
        }
    }

    if i < len(a) {
        ans = append(ans, a[i:]...)
    }
    if j < len(b) {
        ans = append(ans, b[j:]...)
    }
    return ans
}

func quickSort(a [][]int, start int, end int) {

    if start >= end {
        return
    }

    var (
        left  = start - 1
        right = end + 1
        mid   = left + ((right - left) >> 1)
    )

    for left < right {
        left++
        for a[left][0] < a[mid][0] {
            left++
        }

        right--
        for a[right][0] > a[mid][0] {
            right--
        }

        if left < right {
            a[left], a[right] = a[right], a[left]
        }
    }

    quickSort(a, start, right)
    quickSort(a, right+1, end)
}

func readLine(reader *bufio.Reader) string {
    var line, _ = reader.ReadString('\n')
    return strings.TrimRight(line, "\n")
}

func readInt(reader *bufio.Reader) int {
    var a, _ = strconv.Atoi(readLine(reader))
    return a
}

func readArray(reader *bufio.Reader, sep string) []int {
    var line = readLine(reader)
    var strList = strings.Split(line, sep)
    var nums = make([]int, 0)
    var err error
    var v int
    for i := 0; i < len(strList); i++ {
        if v, err = strconv.Atoi(strList[i]); err != nil {
            continue
        }
        nums = append(nums, v)
    }
    return nums
}