一 需求

一个客户拜访某个单位，对这个单位的拜访有开始时间和结束时间，该客户一天可以对多个单位进行拜访，但每两次拜访的间隔不能低于30分钟。需要设计一种算法，判断某次拜访是否能够拜访成功。

二 算法分析

可以用带头节点的单向链表去实现。

三 代码

1 拜访节点

package com.project.domain.vo;

import java.util.Date;

/**
* @className: LocationNode
* @description: 位置节点
* @date: 2021/12/24
* @author: cakin
*/
public class LocationNode {
    /**
     * 拜访类型
     */
    private Integer visitType;

    /**
     * 拜访ID
     */
    private String id;

    /**
     * 开始时间
     */
    private Date startTime;

    /**
     * 结束时间
     */
    private Date endTime;

    private LocationNode next; // 指向下一个节点

    public LocationNode(Integer visitType, String id, Date startTime, Date endTime) {
        this.visitType = visitType;
        this.id = id;
        this.startTime = startTime;
        this.endTime = endTime;
    }

    public Integer getVisitType() {
        return visitType;
    }

    public void setVisitType(Integer visitType) {
        this.visitType = visitType;
    }

    public String getId() {
        return id;
    }

    public void setId(String id) {
        this.id = id;
    }

    public Date getStartTime() {
        return startTime;
    }

    public void setStartTime(Date startTime) {
        this.startTime = startTime;
    }

    public Date getEndTime() {
        return endTime;
    }

    public void setEndTime(Date endTime) {
        this.endTime = endTime;
    }

    public LocationNode getNext() {
        return next;
    }

    public void setNext(LocationNode next) {
        this.next = next;
    }
}

2 链表结构

package com.project.domain.vo;

/**
* @className: SingleLinkedList
* @description: 单向链表
* @date: 2021/12/24
* @author: cakin
*/
public class SingleLinkedList {
    // 先初始化一个头节点, 头节点不能动, 不存放具体的数据
    // 先初始化一个头节点, 头节点不能动, 不存放具体的数据
    private LocationNode head = new LocationNode(0, "", null, null);

    // 返回头节点
    public LocationNode getHead() {
        return head;
    }

    /**
     * 功能描述：添加拜访节点到单向链表
     *
     * @param locationNode 拜访节点
     * @author cakin
     * @date 2021/2/28
     * @description: 添加到尾部
     * 1 找到当前链表的最后节点
     * 2 将最后这个节点的next 指向 新的节点
     */
    public void add(LocationNode locationNode) {
        // 因为 head 节点不能动，因此需要一个辅助变量 temp
        LocationNode temp = head;
        // 遍历链表，找到最后
        while (true) {
            // 找到链表的最后
            if (temp.getNext() == null) {
                break;
            }
            // 如果没有找到最后, 将temp后移
            temp = temp.getNext();
        }
        // 当退出while循环时，temp就指向了链表的最后
        // 将最后这个节点的next指向新的节点
        temp.setNext(locationNode);
    }

    /**
     * 功能描述：检查 locationNode 是否可以插入链表
     *
     * @param locationNode 当前拜访
     * @param realVisitMoveTime 拜访间隔
     * @return boolean 是否可做拜访
     * @author cakin
     * @date 2021/12/24
     * @description: 检查 locationNode 是否可以插入链表
     */
    public boolean checkList(LocationNode locationNode, int realVisitMoveTime) {
        // 判断链表是否为空，说明还没加任务拜访
        if (head.getNext() == null) {
            return true;
        }
        // 因为头节点，不能动，因此我们需要一个辅助变量来遍历
        LocationNode fisrtNode = head.getNext(); // 第一个节点
        LocationNode secondNode; // 第二个节点
        // 第一个节点前是否可以插入
        long intervalTime = fisrtNode.getStartTime().getTime() - locationNode.getEndTime().getTime();
        if (intervalTime >= realVisitMoveTime) {
            return true;
        }
        while (true) {
            // 判断是否到链表最后
            if (fisrtNode == null) {
                break;
            }
            // fisrtNode 不在链表尾
            if (fisrtNode.getNext() != null) {
                secondNode = fisrtNode.getNext();
                long intervalTime1 = locationNode.getStartTime().getTime() - fisrtNode.getEndTime().getTime();
                long intervalTime2 = secondNode.getStartTime().getTime() - locationNode.getEndTime().getTime();
                if (intervalTime1 >= realVisitMoveTime && intervalTime2 >= realVisitMoveTime) {
                    return true;
                }
            } else { // fisrtNode 在链表尾
                intervalTime = locationNode.getStartTime().getTime() - fisrtNode.getEndTime().getTime();
                return intervalTime >= realVisitMoveTime;
            }
            // 将 fisrtNode 后移
            fisrtNode = fisrtNode.getNext();
        }
        return false;
    }
}

3 测试类

import com.project.domain.vo.LocationNode;
import com.project.domain.vo.SingleLinkedList;

import java.util.Date;

public class CheckMoveTime {
    public static void main(String[] args) {
        Integer visitMoveTime = 30;
        // 位移检查逻辑
        if (visitMoveTime != null && visitMoveTime > 0) {
            // 将查到的数据插入单向链表
            // 创建单链表
            SingleLinkedList singleLinkedList = new SingleLinkedList();
            // 第一个节点
            LocationNode locationNode1 = new LocationNode(0, "", new Date(2012, 12, 24, 8, 00), new Date(2012, 12, 24, 9, 00));
            singleLinkedList.add(locationNode1);
            // 第二个节点
            LocationNode locationNode2 = new LocationNode(0, "", new Date(2012, 12, 24, 11, 00),  new Date(2012, 12, 24, 12, 00));
            singleLinkedList.add(locationNode2);
            Date startDate = new Date(2012, 12, 24, 12, 20);
            Date endDate = new Date(2012, 12, 24, 13, 10);
            // 待拜访的数据
            LocationNode locationNode = new LocationNode(0, null, startDate, endDate);
            boolean result = singleLinkedList.checkList(locationNode, 30 * 60 * 1000);
            if (result) {
                System.out.println("拜访成功");
            } else {
                System.out.println("拜访失败");
            }
        }
    }
}

四 运行结果

拜访失败

因为 12:20 距离 12:00 太短 。不符合业务场景。

五 小结

1 在检查前，是需要按拜访的开始时间进行排序的。实际商业项目可从数据库获得排序的数据。

2 对待插入的数据进行合法性检查，可以使用带头节点的单向链表进行实现。