首页 > 顺丰笔试:赏金猎人
头像
iSeven
编辑于 2020-08-21 08:13
+ 关注

顺丰笔试:赏金猎人

只通过了测试用例,来不及写上去,分享一下。各位大佬看看有没有问题
package exam;

import java.util.ArrayList;
import java.util.Scanner;

public class shunfeng {

    //第一层循环循环链表中的每一个数组,表示第一次插入的时间序列
    //第二从循环开始,依次循环后面的数组,如果和前面的链表不相交,表明不冲突,添加进链表
    //第二层循环结束,得到可以的时间序列,把金额算出来
    //第一层循环结束,依次对比可以序列的金钱,拿到最大的一个
    public static int getMaxMoney(ArrayList<Integer[]> list) {
        if (list.size() == 0) {
            return 0;
        }

        if (list.size() == 1) {
            return list.get(0)[2];
        }

        int MaxMoney = Integer.MIN_VALUE;



        for (int i = 0; i < list.size(); i++) {
            ArrayList<Integer[]> temp = new ArrayList<>();
            temp.add(list.get(i));

            for (int j = i + 1; j < list.size(); j++) {
                if (!lianbiaoxiangjiao(temp, list.get(j))) {
                    temp.add(list.get(j));
                }
            }
            if (getListMoney(temp) > MaxMoney) {
                MaxMoney = getListMoney(temp);
            }
        }

        return MaxMoney;
    }

    /**
     * 得到成功的时间序列的金钱
     * @param list
     * @return */
    public static int getListMoney(ArrayList<Integer[]> list) {
        int ans = 0;
        for (int i = 0; i < list.size(); i++) {
            ans = ans + list.get(i)[2];
        }

        return ans;
    }

    /**
     * 判断两个数组是否相交
     * 相交表示时间冲突,不相交表示时间不冲突
     * @param a
     * @param b
     * @return */
    public static boolean xianduanxiangjiao(Integer[] a, Integer[] b) {
        if (a[0] <= b[0] && a[1] >= b[1]) return true;

        if (a[0] >= b[0] && a[1] <= b[1]) return true;

        if (a[0] < b[1] && a[1] >= b[1]) return true;

        if (a[1] > b[0] && b[0] >= a[0]) return true;

        return false;
    }

    /**
     * 判断一个链表中的数组和新的数组是否相交
     * 相交表示时间冲突,不相交表示时间不冲突
     * @param list
     * @param array
     * @return */
    public static boolean lianbiaoxiangjiao(ArrayList<Integer[]> list, Integer[] array) {

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < list.size(); i++) {
            if (list.get(i)[0] < min) {
                min = list.get(i)[0];
            }
            if (list.get(i)[1] > max) {
                max = list.get(i)[1];
            }

            if (xianduanxiangjiao(list.get(i), array)) {
                return true;
            }
        }

        if (array[0] <= min && array[1] >= max) return true;

        return false;


    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        ArrayList<Integer[]> nums = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            Integer[] a = new Integer[3];
            for (int j = 0; j < 3; j++) {
                a[j] = scanner.nextInt();
            }
            nums.add(a);
        }

        int ans = 0;
        ans = getMaxMoney(nums);
        System.out.println(ans);

    }

}


全部评论

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

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐