两道算法题

题目一聚会分组

题目描述：

n个人要一起参加聚会，其中有些人是互相认识的，问能否将参会的人分成两组并且每组的人互相都不认识。

如4个人， 1认识2， 2认识3， 3认识4 就可以1和3 分一组，2和4分一组，
如果2同时认识3和4，那么就无法进行分组。

题目分析：

将每个人看做一个节点，互相认识的节点用线给连接去起来，这样所有有直接或者间接关系的节点就会组成一个图。

然后使用BFS的方式来便利这个图中的每一个节点，并且在遍历的过程中进行分组，分组的信息可以存储在两个HashSet中。

如果当前节点是组A，那么它所有的连接节点都应该分到组B。
如果发现当前节点的一个连接节点已经分到了和当前节点在同一个组，那么就说明无法按题目要求进行分组了，可以直接返回false。

需要注意的是，上述方式形成的图可能有多个。如多组人，每组中的人都只认识自己组中的人，那么每组人都会形成一个单独的图。

多个图并不会影响上面的解题思路，因为不同图之间是没有影响的，无论图A是如何分组的都不影响图B的分组。

代码：

boolean canDivide(int n, List<List<Integer>> relations) {
        // 创建一个HashSet数组，将跟 i 认识的人都存储到数组中下标为 i 的HashSet中
        HashSet<Integer>[] next = new HashSet[n + 1];
        for (List<Integer> relation : relations) {
            int p1 = relation.get(0);
            int p2 = relation.get(1);
            if (next[p1] == null) {
                next[p1] = new HashSet<>();
            }
            if (next[p2] == null) {
                next[p2] = new HashSet<>();
            }
            next[p1].add(p2);
            next[p2].add(p1);
        }
        // 创建两个分组
        HashSet<Integer> s1 = new HashSet<>();
        HashSet<Integer> s2 = new HashSet<>();
        boolean[] visited = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            // 这个人跟所有的人都不认识，所以随便分哪一组都不会有影响，可以直接略过
            if (next[i] == null) continue;
            // 这个人已经分好组了，无需再去判断
            if (s1.contains(i) || s2.contains(i)) continue;
            
            // 这里发现了一个新的图，BFS遍历图中所有的节点。
            Queue<Integer> queue = new LinkedList<>();
            queue.offer((i));
            // 默认放在分组1中
            s1.add(i);
            boolean currentS1 = true;
            while (!queue.isEmpty()) {
                int size = queue.size();
                // BFS遍历这一层中所有的节点
                while (size-- > 0) {
                    int current = queue.poll();
                    // 一个优化，这个节点在之前的层已经被遍历过了，无需再次遍历一遍
                    if (visited[current]) continue;
                    visited[current] = true;
                    for (int p : next[current]) {
                        if (currentS1) {
                            // 当前节点在分组1中，但是s1中已经包含了其相邻的节点，无法完成分组。
                            if (s1.contains(p)) return false;
                            // 将相邻的节点都分到组2中。
                            s2.add(p);
                        } else {
                            if (s2.contains(p)) return false;
                            s1.add(p);
                        }
                        queue.offer(p);
                    }
                }
                // 遍历完一层后，交换在下一层中需要使用的分组。
                currentS1 = !currentS1;
            }
        }
        return true;
    }

题目二值班表分组

题目描述：

一天有24个小时，每个人都有一个自己值班的时间段，而且开始结束时间都是整点(不考虑跨过0点的情况)，如2点到4点，需要找到所有人值班表所能形成的时间段以及每个时间段里都有谁值班。

如

A: 5点到6点

B: 7点到8点

C: 3点到5点

D: 0点到6点

E: 1点到2点

得出的结果应该是

0点到1点：D

1点到2点：D,E

2点到3点：D,

3点到5点：C,D

5点到6点：A,D

7点到8点：B

题目分析

这道题目需要分两步来解决，第一步确定所有人值班表所能形成的时间段，第二步找出没一个时间段都有谁在值班。

对于第一步，首先要明确怎么才能找出合法的时间段，如果两个时间段 5-6， 7-8，那么6-7就不是一个合法的时间段，但是如果
多了一个5-8那么6-7因为有人在值班，就变成了一个合法的时间段。那如何确定某个时间段是否有人在值班呢？

每个人的时间段都有开始时间和结束时间，如果将开始时间看做是一个左括号，结束时间看过是一个右括号，那么当一个时间段左括号
的数目大于右括号的时候，这个时间段必然是一个合法的时间段，因为还有右括号就代表着必然还有人的值班时间是覆盖当前时间段的。

所以这个题目就转化为了括号的匹配问题。
这样可以将所有人值班的开始和结束时间放在一起进行排序，同时记录下是否是开始的时间。排好序后遍历所有的时间段并根据上述理论
就可以找出所有合法的时间段。

对于第二步，有了合法的时间段后就可以重复遍历每个人的值班时间，如果值班时间包含了这个时间段，就可以将这个人给添加到这个时间段中。
但是这样的时间复杂度会比较高，每当需要降低一下时间复杂度的时候都要考虑空间换取时间。在这里可以创建一个大小是24的List数组，数组
下标i 代表i 到i+1的时间段。遍历每个人的时间表一次，将人名添加到对应时间点。这样就可以直接将合法时间段所对应的值班人员一下子取出来。

代码：

/**
 * 值班时间段类，代表了一个值班人员和其值班时间段
 */
class OnCall {
    int start;
    int end;
    String person;

    OnCall(int start, int end, String person) {
        this.start = start;
        this.end = end;
        this.person = person;
    }
}

/**
 * 结果类，代表了一个合法的值班时间段和这个时间段内所有的值班人员。
 */
class Result {
    int start;
    int end;
    HashSet<String> persons = new HashSet<>();

    Result(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

/**
 * 时间点类，代表了值班开始和结束的时间点，并且区分是否是开始的时间。
 */
class TimePoint {
    int time;
    boolean isStart;

    TimePoint(int time, boolean isStart) {
        this.time = time;
        this.isStart = isStart;
    }
}

// 算法的入口
List<Result> find(List<OnCall> schedule) {
    List<Result> results = new ArrayList<>();

    ArrayList<String>[] time = new ArrayList[24];
    for(int i = 0; i< time.length; i++){
        time[i] = new ArrayList<>();
    }

    // 时间点List，将所有人的开始和结束时间放入List中
    ArrayList<TimePoint> timePoints = new ArrayList<>();
    for (OnCall onCall : schedule) {
        timePoints.add(new TimePoint(onCall.start, true));
        timePoints.add(new TimePoint(onCall.end, false));

        for (int i = onCall.start; i < onCall.end; i++) {
            time[i].add(onCall.person);
        }
    }

    // 按时间点进行升序排序
    Collections.sort(timePoints, Comparator.comparingInt(p -> p.time));

    int startCount = 0;
    int preTimePoint = 0;
    for (int i = 0; i < timePoints.size(); i++) {
        TimePoint point = timePoints.get(i);

        // startCount == 0 代表一个新的时间段的开始或者前一个时间段的结束
        if (startCount == 0) {
            preTimePoint = point.time;
            startCount++;
            continue;
        }

        // 根据时间点的属性来增加或者减少startCount
        if (point.isStart) startCount++;
        else startCount--;

        if(point.time == preTimePoint) continue;

        // 找到了一个合法的时间段
        Result result = new Result(preTimePoint, point.time);
        // 将所有处于这个时间段的值班人员放入结果中
        for (int j = preTimePoint; j < point.time; j++) {
            result.persons.addAll(time[j]);
        }
        results.add(result);
        // 当前的时间点可能是下一个合法时间段的开始
        preTimePoint = point.time;
    }
    return results;
}

题目一 聚会分组

题目二 值班表分组

题目一聚会分组

题目二值班表分组