首页 > 7.21华为机试第一题review
头像
菜鸟小美
发布于 2021-07-22 21:40
+ 关注

7.21华为机试第一题review

/*只需要关注结束的时间,按照时间排序,以开始时间为第一权重,结束时间为第二权重,从小到大排序
然后判断当前乘客开始时间是否小于上一位乘客的结束时间,如果小于,需要一辆新的出租车,如果不小于,更新pre,(更新为最大值)
贪心
*/
public class Main {
    //1、第一题
    //求重叠区间的最多个数(也不太算,不知道怎么描述)
    public static void main(String[] args) {
        //输出参数3个
        //第一个参数表示上车时刻,第二个参数上次的站点,第三个参数下车的站点
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int K = scanner.nextInt();

        Nodes[] nodes = new Nodes[K];
        for (int i = 0; i < K; i++) {
            nodes[i] = new Nodes();
            nodes[i].start = scanner.nextInt();

            int num1 = scanner.nextInt();
            int num2 = scanner.nextInt();

           if (num1 == num2){
               //不处理
               //nodes[i] = null;
               //处理一下,要不然给后面埋坑
               nodes[i].end = nodes[i].start;
               continue;
           }else {
               nodes[i].end = Math.min((num2 - num1),N - (num2 - num1)) * 5 + nodes[i].start;
           }
        }

        //对数据进行排序,按照开始时间为第一权重,结束时间为第二权重排序
        Arrays.sort(nodes,0,K,new MyCmp());//又学到了数组可以这样排序

        //开始比较,如果当前乘客的开始时间小于上一个乘客结束时间,需要新的出租车,不小于,则取最大值(开始时间)(缩小范围)
        int i = 0;
        int pre = nodes[0].start;
        int ans = 0;
        while (i < K && nodes[i].start == nodes[i].end) i++;//不处理,直接忽略
        if (i < K){
            ans++;//先肯定有一辆出租车
            pre = nodes[i].start;//重置开始位置
        }
        for (;i < K;i++){
            if (nodes[i].start == nodes[i].end) continue;//忽略
            if (nodes[i].start < pre){
                ans++;//需要新的出租车
                pre = nodes[i].end;
            }else {
                //更新
                pre = Math.max(pre,nodes[i].end);
            }
        }
        System.out.println(ans);
    }
}
class Nodes{
    int start;
    int end;
}
class MyCmp implements Comparator<Nodes>{
    @Override
    public int compare(Nodes o1, Nodes o2) {
        if (o1.start == o2.start){
            return o1.end - o2.end;
        }
        return o1.start - o2.start;
    }
}

全部评论

(11) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期精华帖

热门推荐