包子大道消息
快手开始给美国人民发钱了，Zynn看视频就有钱赚，一路顶上了Free App的榜首，不过视频质量有些堪忧，让包子君连刷抖音和tiktok的心情都没有了，也算是间接打击了对手吧。爱屋及乌，恶其余胥吧
最近美国各个州的起义反抗活动一波接着一波，反正包子君写得也没人看，就当给自己写一个journal啦。【仅代表包子君行者自己的观点】
作为华人美国的老中，包括ABC，至少在包子君公司少数民族的层面，没有什么动静，(哎，至少出来支持一下, 警察这么做就是不对的, los amigos和LGBT都站出来了)。我参加了一个公司黑人的impromptu的Listening session，很多黑人兄弟姐妹share自己亲人的故事，听得我老泪纵横。动乱打砸抢我觉得是不对的，但是如果有人对于这个警察的举动无动于衷，就真的过分了。我最一开始看到照片没觉得，以为压得是脑袋，还和朋友说还好吧，后来看了视频，尤其是George在求饶”I can’t breathe”的时候，触动感太强，是非一目了然。
包子君跟黑人兄弟们的接触跟大多数老中大概差不多，可能就仅仅限于工作中鲜有的接触，比如recruting，finance，legal，程序员比较少，大部分水平正常有几个略担忧，但是这也不能代表什么，sample size，就像也不是所有白人老中程序员水平都很高一样。
开始扯得远一些，美国最牛B的地方就是能够吸引不同种族国家的人为uncle sam打工。现在对于黑人，制度上应该是没有明面的歧视，但是在大家心里还是有一个unconscious biased (比如amy cooper）, 有些bias可能是个优势，身强体壮，能歌善舞，战斗力超群，JJ大，但是有的就是很大的劣势，可能是罪犯，可能不聪明。亚洲人也一样，聪明，数学好(然而并没有, 中国14亿人怎么可能都数学好，只是出国学理工的数学好一点罢了），但是抠门，开车不行，JJ小(sorry guys)。
其实在国内也一样，虽然我们是一个race，但是智人就是有划分部落帮派的属性。我记得我很小的时候，那时候在东北大家还对南方人有bias，精于算计不讲义气还不能喝酒，等我去了南方，发现南方人对于北方人也有bias，傻大粗不懂经营就知道喝酒(虽然后来我发现很多南方同学比我能喝太多了。。。）如果取长补短，求同存异，让自己精于算计还讲义气又tm能喝，岂不无敌了？
黑人的问题是一个很复杂很大的话题。中国有句话，有一定的道理但是也值得商榷，叫做可怜之人必有可恨之处，也许不一定是这个人可恨，也可能是其他东西可恨导致ta可恨。有些观点认为对于黑人的问题可能觉得是他们自己懒，好吃懒做，还总entitled想得到些什么，你看为什么就没有亚洲人或者是老墨homeless，为什么都是老黑？其实你去看看，主要是白人和黑人，跟种族没关系，跟收入和阶层有关。这么多年美国的制度和unconsicious bias让他们很难翻身，就跟中国现在寒门越来越难出贵子一样的道理，大家可以看看美国多年前的一个blue eye & brown eye 的实验https://youtu.be/oGvoXeXCoUY，恶性循环一旦开始，很难跳出去。
Ramble了这么多，就是想说，我们都是unconscious biased，任何时候任何种族都一样，是我们的认知。能做的尽量抛开这些bias，平和的心态多去了解一下对方，regardless对方的race和background，消除误会，求同存异，互利互存。
露个脸吧，之前参加公司帮助under represented colleague kids的一个讲座。It’s a long journey，希望有一天真的可以实现”people will not be judged by the color of their skin, but by the content of their character”
Google Code Jam 2020 Qualification Round: Parenting Partnering Returns Solution
Blogger: http://blog.baozitraining.org/2020/05/google-code-jam-2020-qualification-parenting-returns.html
Youtube: https://youtu.be/OIqAVmD1RGk
博客园: https://www.cnblogs.com/baozitraining/p/12869433.html
B站: https://www.bilibili.com/video/BV1aT4y1u7BU/
【所有包子大道消息图片均来源于网络，版权归原作者所有】
Problem Statement
Problem
Cameron and Jamie’s kid is almost 3 years old! However, even though the child is more independent now, scheduling kid activities and domestic necessities is still a challenge for the couple.
Cameron and Jamie have a list of N activities to take care of during the day. Each activity happens during a specified interval during the day. They need to assign each activity to one of them, so that neither of them is responsible for two activities that overlap. An activity that ends at time t is not considered to overlap with another activity that starts at time t.
For example, suppose that Jamie and Cameron need to cover 3 activities: one running from 18:00 to 20:00, another from 19:00 to 21:00 and another from 22:00 to 23:00. One possibility would be for Jamie to cover the activity running from 19:00 to 21:00, with Cameron covering the other two. Another valid schedule would be for Cameron to cover the activity from 18:00 to 20:00 and Jamie to cover the other two. Notice that the first two activities overlap in the time between 19:00 and 20:00, so it is impossible to assign both of those activities to the same partner.
Given the starting and ending times of each activity, find any schedule that does not require the same person to cover overlapping activities, or say that it is impossible.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing a single integer N, the number of activities to assign. Then, N more lines follow. The i-th of these lines (counting starting from 1) contains two integers Si and Ei. The i-th activity starts exactly Si minutes after midnight and ends exactly Ei minutes after midnight.
Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is IMPOSSIBLE if there is no valid schedule according to the above rules, or a string of exactly N characters otherwise. The i-th character in y must be C if the i-th activity is assigned to Cameron in your proposed schedule, and J if it is assigned to Jamie.
If there are multiple solutions, you may output any one of them. (See “What if a test case has multiple correct solutions?” in the Competing section of the FAQ. This information about multiple solutions will not be explicitly stated in the remainder of the 2020 contest.)
Limits
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
0 ≤ Si < Ei ≤ 24 × 60.
Test set 1 (Visible Verdict)
2 ≤ N ≤ 10.
Test set 2 (Visible Verdict)
2 ≤ N ≤ 1000.
Sample
Input
Output
4
3
360 480
420 540
600 660
3
0 1440
1 3
2 4
5
99 150
1 100
100 301
2 5
150 250
2
0 720
720 1440Case #1: CJC
Case #2: IMPOSSIBLE
Case #3: JCCJJ
Case #4: CC
Sample Case #1 is the one described in the problem statement. As mentioned above, there are other valid solutions, like JCJ and JCC.
In Sample Case #2, all three activities overlap with each other. Assigning them all would mean someone would end up with at least two overlapping activities, so there is no valid schedule.
In Sample Case #3, notice that Cameron ends an activity and starts another one at minute 100.
In Sample Case #4, any schedule would be valid. Specifically, it is OK for one partner to do all activities.
Video Tutorial
You can find the detailed video tutorial here
Thought Process
If you remember the leetcode “merge interval” question, this is quite similar. Baozi Training “Merge Interval”
Model the time range in internal, sort the intervals in ascending order based on the start time, then schedule either “C” or “J” as long as they are available. Update the end time with the assigned task.
The only caveat is we have to remember the original task index for output purpose because we sort the interval using the start time.
An alternate solution is a “bipartite graph coloring” problem. In essence, model the interval into an interval graph. Each interval is a vertex in the graph, and if it overlaps with another interval, there would be an edge. Now the problem becomes starting with one node, if we could color the nodes in two colors without any conflicts. Note the graph doesn’t need to be fully connected, a simple BFS with a visited hash map should do the trick. https://www.geeksforgeeks.org/bipartite-graph/
The time complexity of “bipartite graph coloring” is O(V+E)
Solutions
Greedy solution
1 import java.io.BufferedReader;
2 import java.io.InputStreamReader;
3 import java.util.*;
4
5 public class Solution {
6 public static void main(String[] args) {
7 Scanner s = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
8
9 int testCases = s.nextInt();
10 int caseNum = 1;
11 Solution p = new Solution();
12
13 while (caseNum <= testCases) {
14 int n = s.nextInt();
15 int[][] a = new int[n][2];
16 for (int i = 0; i < n; i++) {
17 for (int j = 0; j < 2; j++)
18 a[i][j] = s.nextInt();
19 }
20 System.out.println(String.format("Case #%d: %s", caseNum, p.calSchedule(a)));
21
22 caseNum++;
23 }
24 }
25
26 private String calSchedule(int[][] scheudle) {
27 if (scheudle == null || scheudle.length == 0 || scheudle[0].length == 0) {
28 return null;
29 }
30
31 List<IntervalWithIndex> l = new ArrayList<>();
32 for (int i = 0; i < scheudle.length; i++) {
33 l.add(new IntervalWithIndex(scheudle[i][0], scheudle[i][1],i));
34 }
35
36 Collections.sort(l);
37
38 int cEndTime = Integer.MIN_VALUE;
39 int jEndTime = Integer.MIN_VALUE;
40
41 char[] result = new char[l.size()];
42
43 for (int i = 0; i < l.size(); i++) {
44 IntervalWithIndex it = l.get(i);
45 if (it.start >= cEndTime) {
46 result[it.originalIndex] = 'C';
47 cEndTime = it.end;
48 } else if (it.start >= jEndTime) {
49 result[it.originalIndex] = 'J';
50 jEndTime = it.end;
51 } else {
52 return "IMPOSSIBLE";
53 }
54 }
55 StringBuilder sb = new StringBuilder();
56 for (char c : result) {
57 sb.append(c);
58 }
59
60 return sb.toString();
61 }
62
63 private class IntervalWithIndex implements Comparable<IntervalWithIndex> {
64 public int start;
65 public int end;
66 public int originalIndex;
67
68 public IntervalWithIndex(int start, int end, int originalIndex) {
69 this.start = start;
70 this.end = end;
71 this.originalIndex = originalIndex;
72 }
73
74 // natural ordering ascending
75 public int compareTo(IntervalWithIndex t) {
76 return this.start - t.start;
77 }
78 }
79 }Time Complexity: O(lgN) since we sort
Space Complexity: O(N) since we used extra list for the intervals