LeetCode 1204. 最后一个能进入巴士的人

Categories:

题目描述
思路分析
1. 解法一：按顺序累加体重（推荐）
相似题目

题目描述

✅ 1204. 最后一个能进入巴士的人

思路分析

解法一：按顺序累加体重（推荐）

核心思路：

按 turn 升序排序队列，模拟依次上车。

维护累计体重 sum，若加入当前乘客后超过容量，则停止。

记录最后一个满足 sum <= 1000 的乘客姓名。

复杂度分析：

时间复杂度：O(n log n)，排序为主。

空间复杂度：O(n)，存储排序后的队列。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class Solution {
    public String lastPersonToFit(List<Person> people) {
        List<Person> list = new ArrayList<>(people);
        Collections.sort(list, Comparator.comparingInt(a -> a.turn));

        int sum = 0;
        String last = "";
        for (Person p : list) {
            if (sum + p.weight > 1000) {
                break;
            }
            sum += p.weight;
            last = p.name;
        }
        return last;
    }

    static class Person {
        String name;
        int weight;
        int turn;

        Person(String name, int weight, int turn) {
            this.name = name;
            this.weight = weight;
            this.turn = turn;
        }
    }
}

import "sort"

type Person struct {
    Name   string
    Weight int
    Turn   int
}

func lastPersonToFit(people []Person) string {
    list := make([]Person, len(people))
    copy(list, people)

    sort.Slice(list, func(i, j int) bool {
        return list[i].Turn < list[j].Turn
    })

    sum := 0
    last := ""
    for _, p := range list {
        if sum+p.Weight > 1000 {
            break
        }
        sum += p.Weight
        last = p.Name
    }
    return last
}

相似题目

题目	难度	考察点
1094. 拼车	中等	前缀和
1109. 航班预订统计	中等	差分数组
183. 从不订购的客户	简单	数据库查询
184. 部门工资最高的员工	中等	数据库查询
177. 第N高的薪水	中等	数据库查询

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/22314173