sort #

type Interface interface {
    // Len is the number of elements in the collection.
    Len() int
    // Less reports whether the element with
    // index i should sort before the element with index j.
    Less(i, j int) bool
    // Swap swaps the elements with indexes i and j.
    Swap(i, j int)
}

// 内部实现的四种排序算法
// 插入排序
func insertionSort(data Interface, a, b int)
// 堆排序
func heapSort(data Interface, a, b int)
// 快速排序
func quickSort(data Interface, a, b, maxDepth int)
// 归并排序
func symMerge(data Interface, a, m, b int)

// https://leetcode.cn/problems/non-overlapping-intervals/

import "sort"

func eraseOverlapIntervals(intervals [][]int) int {
    arr := _sort(intervals)
    tmp := arr[0]
    var ret int
    for i:=1; i< len(arr); i++{
        if tmp[1] > arr[i][0]{
            ret++
        }else{
            tmp = arr[i]
        }
    }
    return ret
}

func _sort(s [][]int)[][]int{
    sort.Sort(slice(s))
    return s
}

type slice [][]int
func (s slice)Len()int{
    return len(s) 
}

func (s slice)Swap(i, j int){
    s[i], s[j] = s[j], s[i]
}

func (s slice)Less(i, j int)bool{
   if s[i][1] < s[j][1]{
       return true
   }
   return false
}

sort.Strings()
sort.Ints()

package main

import (
    "fmt"
    "sort"
)

func main() {

    strs := []string{"c", "a", "b"}
    sort.Strings(strs)
    fmt.Println("Strings:", strs)

    ints := []int{7, 2, 4}
    sort.Ints(ints)
    fmt.Println("Ints:   ", ints)

    s := sort.IntsAreSorted(ints)
    fmt.Println("Sorted: ", s)
}

sort.Slice(x any, less func(i, j int)bool)

func eraseOverlapIntervals(intervals [][]int) (res int) {
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][1] < intervals[j][1]
	})
	curMax := intervals[0][1]
	for i := 1; i < len(intervals); i++ {
		if intervals[i][0] >= curMax {
			curMax = intervals[i][1]
		} else {
			res++
			if intervals[i][1] <= curMax {
				curMax = intervals[i][1]
			}
		}
	}
	return
}