小米汽车

昨天晚上雷军终于公布了小米汽车的价格。

• 标准版：21.59W
• Pro 版：24.59W
• Max 版：29.99W

此前外界的普遍预期是 23W25W，实际公布价格比预期要低 24W，自然是平地一声雷。

"雷神"二字不仅刷爆了各个平台的直播间弹幕，同时也登上了微博热搜：

其实昨晚发布会正式开始前，部分论坛和朋友圈就 PO 出了雷军（带汽车价格）的彩排照：

然后发布会一开始，我重点留意了一下雷军穿的衣服，和爆料图中的一模一样，当时心里就凉了一截。

带着「雷军，你快说啊」的忐忑心情，又听了近 2 个小时的详细介绍。

还好最后公布的价格，确实对得起米粉们的期待。

我不是米粉，但是对雷军的个人印象还算可以。

小米作为全国顶尖的制造业公司，又有着鲜明的互联网基因，有自己独到的产品思维，入局造车，或许真的能在 3~5 年成为牌桌上的选手。

可惜今天 H 股那边休市，不然还真的想看看资本是怎么投票的。

发布会上，雷军提到小米汽车卖这个价格，是要亏钱的。

虽然对车圈了解不深，没法从成本角度去辨别，但这话我是真的信。

首先雷老板就是老实人，别人都是说是几百万、一千万以内最好的车，最终卖个大几十万，雷老板就说 50W 以内最好，最终 22W 不到。

真诚，就是小米的护城河。

其次，要想知道 22W 是不是真亏钱，可以对标国内屠夫 BYD 的旗舰轿车汉 EV 是什么价格，就大概知道了。

差不多续航的汉 EV 也要 21.98W，这可是卖了很多年的汉。

小米前期的产能爬坡阶段，卖 21.59W，说亏钱，可太合理了。

价格有惊喜，市场自然会有好的反应。

在 22:00 正式开售之后，4 分钟定金数破 1W，7 分钟定数破 2W。

不过小米的小编搞错了一基本概念：大定通常是指不能退的，而小米除了 5000 台创始版以外，都是定金 7 天可退，所以破的是"小定"，不是"大定"。

最后再来看一眼小米汽车，真挺好看：

...

回归主线。

来一道和「小米」相关的算法原题。

题目描述

平台：LeetCode

题号：1235

你打算利用空闲时间来做兼职工作赚些零花钱。

这里有 n 份兼职工作，每份工作预计从 startTime[i] 开始到 endTime[i] 结束，报酬为 profit[i]。

给你一份兼职工作表，包含开始时间 startTime，结束时间 endTime 和预计报酬 profit 三个数组，请你计算并返回可以获得的最大报酬。

注意，时间上出现重叠的 2 份工作不能同时进行。

如果你选择的工作在时间 X 结束，那么你可以立刻进行在时间 X 开始的下一份工作。

示例 1：

输入：startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]

输出：120

解释：
我们选出第 1 份和第 4 份工作， 
时间范围是 [1-3]+[3-6]，共获得报酬 120 = 50 + 70。

示例 2：

输入：startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]

输出：150

解释：
我们选择第 1，4，5 份工作。 
共获得报酬 150 = 20 + 70 + 60。

示例 3：

输入：startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]

输出：6

提示：

• $1 <= startTime.length == endTime.length == profit.length <= 5 \times 10^4$
• $1 <= startTime[i] < endTime[i] <= 10^9$
• $1 <= profit[i] <= 10^4$

序列 DP + 二分

为了方便，我们令 startTime 为 st，endTime 为 endTime，profit 为 ps，同时定义三元组 $job[i] = (st[i], et[i], ps[i])$ 来代指某份工作。

我们知道，在理想情况下，若能将所有工作排成不重叠的直线，我们便能通过完成所有工作来取得最大收益。

归结到每个工作，我们总有「选择完成该工作」和「选择不完成该工作」两种决策。

定义 $f[i]$ 为考虑前 $i$ 个工作，所能取得的最大收益（注意 $job[i]$ 不一定被选择完成），为了方便，我们令下标从 $1$ 开始：

• 当不选择该工作时：由于 $job[i]$ 明确不会产生价值，可知 $f[i] = f[i - 1]$；
• 当选择该工作时：可分为「仅选择完成该工作」或「选择 考虑 将该工作接在某个工作后面完成」两种情况：
  • 当「仅选择完成该工作」时，我们有 $f[i] = job[i][2]$；
  • 当「选择 考虑 将该工作接在某个工作后面完成」时，我们需要在所有满足「$job[j][1] <= job[i][0]$」中选择最适合的 $job[j]$ 接在 $job[i]$ 的前面。 即在所有能够在 $job[i]$ 开始前顺利结束的 $job[j]$ 中取最大的 $f[j]$，此时有 $f[i] = f[j] + job[i][2]$

    需要注意：这里的“接在”是指将 $job[j]$ 纳入考虑，但具体方案中，并不一定选择 $job[j]$ 来执行（好好想想我们的 $f[i]$ 状态定义）

最终 $f[i]$ 为上述三种方案中的最大值，并且最终的 $f[n]$ 即是我们的答案。

当我们处理到 $job[i]$ 时，为了能够「将所有所能拼接在 $job[i]$ 前面的 $job[j]$ 归结到一边」并且「所能更新 $f[i]$ 的 $f[j]$ 均被计算」，我们可以通过对所有的 $job[i]$ 进行右端点（结束时间）进行排升序，并按照从小到大的方式处理每个 $job[i]$。

此处排序的意义有两点：

• 由于我们是根据右端点排序，当我们处理到某个 $job[i]$ 时，由于有 $job[X][0] < job[X][1]$，因此所能接在 $job[i]$ 前面（结束时间小于等于 $job[i]$ 开始时间）的 $job[j]$ 必然位于 $[0, i)$ 之间；
• 由于我们对 $f[i]$ 的定义并不限定了必须选 $job[i]$，因此在 $[0, i)$ 范围内以 $job[j]$ 为分割点的数组的具有「二段性」：坐标范围小于等于 $j$ 的 $job[X]$ 均可“接在” $job[i]$ 前面。因此我们可通过「二分」来找所能接在 $job[i]$ 前面的坐标最大的 $job[j]$。

Java 代码：

class Solution {
    public int jobScheduling(int[] st, int[] et, int[] ps) {
        int n = st.length;
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < n; i++) list.add(new int[]{st[i], et[i], ps[i]});
        Collections.sort(list, (a, b)->a[1] - b[1]);
        int[] f = new int[n + 10];
        for (int i = 1; i <= n; i++) {
            int[] info = list.get(i - 1);
            int a = info[0], b = info[1], c = info[2];
            f[i] = Math.max(f[i - 1], c);
            int l = 0, r = i - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (list.get(mid)[1] <= a) l = mid;
                else r = mid - 1;
            }
            if (list.get(r)[1] <= a) f[i] = Math.max(f[i], f[r + 1] + c);
        }
        return f[n];
    }
}

C++ 代码：

class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n = startTime.size();
        vector<vector<int>> list(n);
        for (int i = 0; i < n; i++) list[i] = {startTime[i], endTime[i], profit[i]};
        sort(list.begin(), list.end(), [](vector<int> a, vector<int> b)->bool{return a[1] < b[1];});
        vector<int> f(n + 10, 0);
        for(int i = 1; i <= n; i++) {
            int a = list[i - 1][0], b = list[i - 1][1], c = list[i - 1][2];
            f[i] = max(f[i - 1], c);
            int l = 0, r = i - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (list[mid][1] <= a) l = mid;
                else r = mid - 1;
            }
            if (list[r][1] <= a) f[i] = max(f[i], f[r + 1] + c);
        }
        return f[n];
    }
};

Python 代码：

class Solution:
    def jobScheduling(self, st: List[int], et: List[int], ps: List[int]) -> int:
        n = len(st)
        jobs = [(st[i], et[i], ps[i]) for i in range(n)]
        jobs.sort(key=lambda x: x[1])
        f = [0] * (n + 10)
        for i in range(1, n + 1):
            a, b, c = jobs[i - 1]
            f[i] = max(f[i - 1], c)
            l, r = 0, i - 1
            while l < r:
                mid = l + r + 1 >> 1
                if jobs[mid][1] <= a:
                    l = mid
                else:
                    r = mid - 1
            if jobs[r][1] <= a:
                f[i] = max(f[i], f[r + 1] + c)
        return f[n]

TypeScript 代码：

function jobScheduling(st: number[], et: number[], ps: number[]): number {
    const n = st.length
    const list = new Array<Array<number>>()
    for (let i = 0; i < n; i++) list.push([st[i], et[i], ps[i]])
    list.sort((a,b)=>a[1]-b[1])
    const f = new Array<number>(n + 10).fill(0)
    for (let i = 1; i <= n; i++) {
        const info = list[i - 1]
        const a = info[0], b = info[1], c = info[2]
        f[i] = Math.max(f[i - 1], c)
        let l = 0, r = i - 1
        while (l < r) {
            const mid = l + r + 1 >> 1
            if (list[mid][1] <= a) l = mid
            else r = mid - 1
        }
        if (list[r][1] <= a) f[i] = Math.max(f[i], f[r + 1] + c)
    }
    return f[n]
}

• 时间复杂度：排序复杂度为 $O(n\log{n})$；DP 过程共有 $n$ 个状态需要转移，每次转移需要进行二分，单次复杂度为 $O(\log{n})$。整体复杂度为 $O(n\log{n})$
• 空间复杂度：$O(n)$

最后

给大伙通知一下 📢 ：

全网最低价 LeetCode 会员目前仍可用！！！

📅 年度会员：有效期加赠两个月！！; 季度会员：有效期加赠两周！！

🧧 年度会员：获 66.66 现金红包！！; 季度会员：获 22.22 现金红包！！

🎁 年度会员：参与当月丰厚专属实物抽奖（中奖率 > 30%)！！

专属链接：https://leetcode.cn/premium/?promoChannel=acoier

更多详情请戳 这里 。

我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。

欢迎关注，明天见。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉