November 20, 2021: the start and end times of a movie can be listed in a small array

2021-11-20： The start and end times of a movie can be represented by a small array "07:30","12:00", It is known that there is 2000 The movie starts and ends on the same day , This day from 00:00 Start to 23:59 end , Be sure to choose 3 A completely conflict free movie to watch , Returns the maximum viewing time . If you can't choose 3 A completely conflict free movie to watch , return -1. From little red book .

answer 2021-11-20：

1. Sort . Sort by start time ; If the start time is the same , Sort by end time .

2. recursive . Three parameters ： minute （<=1440）, Number of movies left （<=33）, What movie number (<=2000).

Time complexity ：10 Of 7 Within the power of .

Spatial complexity ： Sort of .

The code to use golang To write . The code is as follows ：

package main

import (
    "fmt"
    "sort"
)

func main() {
    movies := [][]int{{10, 17}, {18, 19}, {20, 20}}
    ret := maxEnjoy2(movies)
    fmt.Println(ret)
}

func maxEnjoy2(movies [][]int) int {
    sort.Slice(movies, func(i, j int) bool {
        a := movies[i]
        b := movies[j]
        if a[0] != b[0] {
            return a[0] < b[0]
        } else {
            return a[1] < b[1]
        }
    })
    return process2(movies, 0, 0, 3)
}

func process2(movies [][]int, index int, time int, rest int) int {
    if index == len(movies) {
        return twoSelectOne(rest == 0, 0, -1)
    }
    p1 := process2(movies, index+1, time, rest)
    next := twoSelectOne(movies[index][0] >= time && rest > 0, process2(movies, index+1, movies[index][1], rest-1), -1)
    p2 := twoSelectOne(next != -1, (movies[index][1] - movies[index][0] + next), -1)
    return getMax(p1, p2)
}

func twoSelectOne(c bool, a int, b int) int {
    if c {
        return a
    } else {
        return b
    }
}

func getMax(a int, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

The results are as follows ：

picture

Zuo Shen java Code