「算法」贪心算法

 1package main
 2
 3import (
 4	"fmt"
 5	"sort"
 6)
 7
 8type node struct {
 9	startAt int
10	endAt   int
11}
12
13var (
14	total    int
15	now      int
16	res      int
17	nodeList = make([]node, 0)
18)
19
20func main() {
21	_, _ = fmt.Scanf("%d", &total)
22	nodeList = make([]node, total)
23	for i := 0; i < total; i++ {
24		_, _ = fmt.Scanf("%d", &nodeList[i].startAt)
25		_, _ = fmt.Scanf("%d", &nodeList[i].endAt)
26	}
27
28	sort.Slice(nodeList, func(i, j int) bool {
29		return nodeList[i].endAt < nodeList[j].endAt
30	})
31
32	now = 0
33	res = 1
34	for i := 1; i < total; i++ {
35		if nodeList[now].endAt <= nodeList[i].startAt {
36			now = i
37			res++
38			fmt.Printf("%v\n", nodeList[i])
39		}
40	}
41
42	fmt.Printf("%v", res)
43}
44
45/* Input
464
471 3
484 6
492 5
501 7
51
52*/