一、题目

你正在将你的房子放在Airbnb上出租。有很多预订请求。每个请求都表示为一个长度为2的整数数组。第一个元素是开始日期，第二个元素是结束日期。你需要明智地选择预订请求，以便在不冲突的情况下获得最大利润。你可以假设每天的价格是相同的。

二、输入

[n][2]的二维整数数组

三、输出

不冲突排期的最大利润

四、示例

示例一

1
2
3
4
5
输入：
[[1,2], [4,5], [7,7]]

输出：
5

示例二

1
2
3
4
5
输入：
[[4,5], [7,9], [1,100]]

输出：
100

五、题解

  1. 动态规划解法明显
  2. 初始数组排序根据开始点还是结束点排序不重要。因为题解中遍历所有符合条件的前置预定请求，并从所有dp[i]中求最值
  3. 题目不是求最多请求的个数，而是求最大获利（最长不冲突线段长度和）。这个只影响dp[i]值的计算，不影响整体算法框架
  4. 本解法效率有提升空间。因为是遍历所有前置预定请求，时间复杂度达O（n**2)

5.1 Java 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
package org.stone.study.algo.ex202412;

import java.util.Arrays;

/**
 * 你正在将你的房子放在Airbnb上出租。有很多预订请求。每个请求都表示为一个长度为2的整数数组。第一个元素是开始日期，
 * 第二个元素是结束日期。你需要明智地选择预订请求，以便在不冲突的情况下获得最大利润。你可以假设每天的价格是相同的。
 */
public class MaxProfit {
    public static void main(String[] args) {
//        int[][] arr = {{1, 2}, {4, 5}, {7, 7}};
        int[][] arr = {{4, 5}, {7, 9}, {1, 100}};

        int maxProfit = getMaxProfit(arr);
        System.out.println(maxProfit);
    }

    public static int getMaxProfit(int[][] arr) {
        Arrays.sort(arr, (o1, o2) -> o1[0] - o2[0]);

        int n = arr.length;
        // dp[i]表示以i结尾（包括第i条预定请求）的最大利润
        int[] dp = new int[n];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = arr[i][1] - arr[i][0] + 1;
            ans = Math.max(ans, dp[i]);

            for (int j = 0; j < i; j++) {
                if (arr[j][1] <= arr[i][0]) {
                    dp[i] = Math.max(dp[i], dp[j] + arr[i][1] - arr[i][0] + 1);
                    // 答案可能以任何一条预定请求结尾
                    ans = Math.max(ans, dp[i]);
                }
            }
        }

        return ans;
    }
}

5.2 Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 求不冲突排期的最大获利
def getMaxProfit(arr):
    arr.sort(key = lambda o : o[0])
    n = len(arr)
    dp = [ (o[1] - o[0] + 1) for o in arr]
    res = 0
    for i in range(n):
        res = max(res, dp[i])
        for j in range(i):
            if arr[j][1] < arr[i][0]:
                dp[i] = max(dp[i], dp[j] + arr[i][1] - arr[i][0] + 1)
                res = max(res, dp[i])

    return res

if __name__ == '__main__':
    # arr = [[1,2], [4,5], [7,7]]
    arr = [[4,5], [7,9], [1,100]]
    print(getMaxProfit(arr))