leetcode-go/oj/pdd-2019/no3/money.go

package main

import (
	"fmt"
	"sort"
)

type ints [][2]int

func (is ints) Len() int           { return len(is) }
func (is ints) Less(i, j int) bool { return is[i][0] < is[j][0] }
func (is ints) Swap(i, j int)      { is[i], is[j] = is[j], is[i] }

func main() {
	var n, d int
	fmt.Scan(&n, &d)
	var is ints = make([][2]int, n)
	for i := range is {
		fmt.Scan(&is[i][0], &is[i][1])
	}
	sort.Sort(is)
	dp := make([]int, n)
	idx := 0
	dp[0] = -1
	for i := 1; i < n; i++ {
		if is[i][0]-is[idx][0] < d {
			dp[i] = dp[i-1]
			continue
		}
		if pre := dp[i-1]; pre == -1 || is[pre][1] < is[idx][1] {
			dp[i] = idx
		} else {
			dp[i] = dp[i-1]
		}
		idx++
	}
	max := 0
	for i := range dp {
		if dp[i] == -1 {
			continue
		}
		max = maxInt(max, is[i][1]+is[dp[i]][1])
	}
	fmt.Println(max)
}

func maxInt(x, y int) int {
	if x < y {
		return y
	}
	return x
}