博客

算法题：

解决实际应用问题：公交车让座问题

一辆公交车，有n个座位（n<100），陆续有乘客上车和下车，新乘客上车时，如果座位全满，新上来的乘客的优先级如果比座位上的某些人大，那么就需要选出优先级比他低的人给他让座，同样的，座位上有人到站下车空出了座位，需要在无座的人里面选出优先级高的人入座

座位优先级规则（先幼后老再中年）：按年龄最小（年龄相同再按上车时间最先上车优先）安排10岁及以下的儿童入座，如果没有合适的儿童，再安排车上年龄最大的(年龄相同按上车时间最先上车的优先)的人入坐

使用一个二维数组来代表上下车的人 [[姓名,年龄,“上车/下车”],…], 姓名不重复, 数组长度小于10000,年龄小于200，一个人最多只有一次上车和下车记录

# 要求计算出主动让座（正常下车不算让座）的人次姓名清单

def busPrioritySeats(queue: list, n: int) -> list:

# to be implemented

return []

    queue = [["大学生朱菲菲", 20, "上车"],
    ["中年抗压男王五", 40, "上车"],
    ["小学生张三", 6, "上车"],
    ["村花罗密欧", 18, "上车"],
    ["小学生张三", 6, "下车"],
    ["大学生朱菲菲", 20, "下车"],
    ["退伍大爷牛七", 60, "上车"]];

    print(busPrioritySeats(queue, 2))
    # 算法说明：
    # 前2个都有位置入座                    -> 有座：["大学生朱菲菲"，"中年抗压男王五"],无座位：[] , 让座记录:[]
    # 小学生张三 来了，大学生 主动让座     -> 有座：["小学生张三","中年抗压男王五"]， 无座位：["大学生朱菲菲"] , 让座记录:["大学生朱菲菲"]
    # 村花罗密欧来了，村花 无座站岗           -> 有座：["小学生张三","中年抗压男王五"]， 无座位：["大学生朱菲菲","村花罗密欧"] , 让座记录:["大学生朱菲菲"]
    # 小学生张三下车，空出座位给大学生朱菲菲入座 -> 有座：["中年抗压男王五","大学生朱菲菲"]， 无座位：["村花罗密欧"] , 让座记录:["大学生朱菲菲"]
    # 大学生朱菲菲下车，空出座位给村花罗密欧入座 -> 有座：["中年抗压男王五","村花罗密欧"]， 无座位：[] , 让座记录:["大学生朱菲菲"]
    # 退伍大爷牛七上车，村花罗密欧 主动让座     -> 有座：["退伍大爷牛七","中年抗压男王五"]， 无座位：["村花罗密欧"] , 让座记录:["大学生朱菲菲","村花罗密欧"]

使用优先队列的比较器详解见前文

PriorityQueue优先队列中比较器Comparator的使用

public class Main {

    public static void main(String[] args) {
        String[][] peoples  = {{"大学生朱菲菲", "20","上车"},
            {"中年抗压男王五", "40", "上车"},
            {"小学生张三", "6", "上车"},
            {"村花罗密欧", "18","上车"},
            {"小学生张三", "6", "下车"},
            {"大学生朱菲菲", "20", "下车"},
            {"退伍大爷牛七", "60", "上车"}};

        List<String[]> res = busPrioritySeats(peoples,2);

        for(String[] s:res){
            System.out.println(s[0]);
        }

        System.out.println(" ");
    }

    public static int cmp(String[] o1, String[] o2){
        int age1 = Integer.parseInt(o1[1]);
        int age2 = Integer.parseInt(o2[1]);
        //当年龄相同时，我们按照上车的顺序
        //拿上策划的顺序是什么呢？之前说过，如对的时候永远是那新的那个值和其他旧的值进行比较
        //所以o1永远是新来的，所以如果相等，o1是最应该让座的人
        //之前说过入队时想让o1上去，return -1；
        if(age1 == age2){
            return -1;
        }
        //不相等时就开始比较年龄
        else{
            //两者年龄都小于等于10，应该比较大的先让座
            //类似于建立大顶堆，所以 return o2-o1;
            if(age1<=10 && age2<=10){
                return age2-age1;
            }
            //两者年龄都大于10，应该比较小的先让座
            //类似于建立小顶堆，所以 return o1-o2;
            else if(age1>10 && age2>10){
                return age1 - age2;
            }
            //一个小于等于10，一个大于10，也是应该大的先让座
            //类似于建立大顶堆，return o2-o1;
            //应该和第一种合在一起，但是为了观看清晰，就不合了
            else{
                return age2-age1;
            }
        }
    }

    public static List<String[]> busPrioritySeats(String[][] peoples, int n){

        List<String[]> res = new ArrayList< String[]>();

        PriorityQueue<String[]> seats = new PriorityQueue< String[]>(new Comparator<String[]>() {
            @Override
            public int compare(String[] o1, String[] o2) {
                return cmp(o1,o2);
            }
        });
        PriorityQueue<String[]> stand = new PriorityQueue<String[]>(new Comparator<String[]>() {
            @Override
            public int compare(String[] o1, String[] o2) {
                return -cmp(o1,o2);
            }
        });


        for(String[] s: peoples){
            if("上车".equals(s[2])){
                if(seats.size() < n){
                    seats.offer(s);
                }else{
                    String[] people = seats.peek();

                    //通过比较如果不应该让坐就直接将people放如站着的队伍
                    if(cmp(s,people)<0){
                        stand.offer(s);
                    }else{
                        res.add(people);
                        seats.poll();
                        seats.offer(s);
                        stand.offer(people);
                    }
                }
            }else {
                //people没座位，从stand中移除
                String[] temp = valid(stand,s[0]);
                if(temp != null){
                    stand.remove(temp);
                }
                //people有作为，从seats中移除并从stand中找出一个放到seats中
                else{
                    temp = valid(seats,s[0]);
                    seats.remove(temp);
                    if(stand.size() > 0){
                        seats.offer(stand.poll());
                    }
                }
            }
        }
        return res;
    }

    public static String[] valid(PriorityQueue<String[]> queue,String name){
        for(String[] s:queue){
            if(s[0].equals(name)){
                return s;
            }
        }
        return null;
    }
    
}