github-allen
diff --git a/‎Java/2 Sum.java
Lines changed: 11 additions & 13 deletions b/‎Java/2 Sum.java
Lines changed: 11 additions & 13 deletions
diff --git a/‎Java/H-Index.java
Lines changed: 1 addition & 1 deletion b/‎Java/H-Index.java
Lines changed: 1 addition & 1 deletion
diff --git a/‎Java/Insert Interval.java
Lines changed: 40 additions & 52 deletions b/‎Java/Insert Interval.java
Lines changed: 40 additions & 52 deletions
@@ -42,21 +42,19 @@ Always check (target - current) from the HashMap.
 */
 class Solution {
     public int[] twoSum(int[] nums, int target) {
-        if (nums == null || nums.length == 0) {
-            return null;
-        }
-        int[] result = new int[2];
-        Map<Integer, Integer> recordMap = new HashMap<>();
+        int[] rst = new int[2];
+        if (nums == null || nums.length <= 1) return rst;
+
+        Map<Integer, Integer> map = new HashMap<>();
         for (int i = 0; i < nums.length; i++) {
-            if (recordMap.containsKey(target - nums[i])) {
-                result[0] = recordMap.get(target - nums[i]);
-                result[1] = i;
-                return result;
-            } else {
-                recordMap.put(nums[i], i);
-            }
+            if (map.containsKey(target - nums[i])) {
+                rst[0] = map.get(target - nums[i]);
+                rst[1] = i;
+                break;
+            } 
+            map.put(nums[i], i);
         }
-        return result;
+        return rst;
     }
 }
 
 
@@ -19,7 +19,7 @@
 
 #### Bucket count / Bucket Sort
 - O(n)
-- Bucket sort的思想: 过一遍 input, 把dictation value 作为 index, 分布在bucket[index]上++
+- Bucket sort的思想(更像是counting sort?): 过一遍 input, 把dictation value 作为 index, 分布在bucket[index]上++
 - bucket[x] 是 count when # of citation == x. 
 - 如果 x 大于 n的时候, 就超出了index范围, 但是刚好这个问题可以包容, 把这样的情况记位在bucket[n]就可以
 - 巧妙: `sum += bucket[h]` where `h = [n ~ 0]` 利用了h-index的definition:
 
@@ -10,7 +10,7 @@
 
 
 #### Basic Implementation
-- 这里已经给了sorted intervals by start point.
+- 这里已经给了 **sorted** intervals by start point.
 - 直接找到可以insert newInterval的位子. Insert
 - 然后loop to merge entire interval array
 - 因为给的是个list, 所以方便`intervals.remove(i)`
@@ -58,80 +58,68 @@
 2. sort point in min-heap
 3. when count increase and decreases to 0, that means we can close an interval
 */
-/**
- * Definition for an interval.
- * public class Interval {
- *     int start;
- *     int end;
- *     Interval() { start = 0; end = 0; }
- *     Interval(int s, int e) { start = s; end = e; }
- * }
- */
-public class Solution {
-
+/*
+Option1: 
+- convert all intervals into points with open/close flag, sort, and merge. When count == 0, close a interval.
+- priority queue, O(n) space, O(nlogn) time
+*/
+class Solution {
     class Point {
-        int x;
-        int flag;
-        public Point(int x, int flag) {
-            this.x = x;
+        int val, flag;
+        public Point(int val, int flag) {
+            this.val = val;
             this.flag = flag;
         }
     }
     public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
         List<Interval> rst = new ArrayList<>();
-        if (intervals == null && newInterval == null) {
-            return rst;
-        } else if (intervals == null) {
-            rst.add(newInterval);
+        if (intervals == null || intervals.size() == 0 || newInterval == null) {
+            if (newInterval != null) rst.add(newInterval);
             return rst;
-        } else if (newInterval == null) {
-            return intervals;
         }
-
-        PriorityQueue<Point> queue = new PriorityQueue<>(1, new Comparator<Point>(){
-            public int compare(Point a, Point b){
-                return a.x - b.x;
-            }
-        });
-
-        for (Interval range: intervals) {
-            queue.add(new Point(range.start, 1));
-            queue.add(new Point(range.end, -1));
-        }
-
-        queue.add(new Point(newInterval.start, 1));
-        queue.add(new Point(newInterval.end, -1));
-
+        
+        // build priority queue
+        PriorityQueue<Point> queue = buildQueue(intervals, newInterval);
+        // iterate over queue, count and build interval
         int count = 0;
-        int startNew = 0;
-        int endNew = 0;
+        Interval interval = new Interval();
         while (!queue.isEmpty()) {
             Point p = queue.poll();
-            if (count == 0) {
-                startNew = p.x;
-            }
+            if (count == 0) {//detect start
+                interval.start = p.val;
+            }    
+            
             count += p.flag;
-
-            while (!queue.isEmpty() && p.x == queue.peek().x) {
+            while (!queue.isEmpty() && p.val == queue.peek().val) {
                 p = queue.poll();
                 count += p.flag;
             }
-
+            
             if (count == 0) {
-                endNew = p.x;
-                Interval addInterval = new Interval(startNew, endNew);
-                rst.add(addInterval);
+                interval.end = p.val;
+                rst.add(interval);
+                interval = new Interval();
             }
-
-        }//end while
-
+        }
         return rst;
-
     }
+    
+    private PriorityQueue<Point> buildQueue(List<Interval> intervals, Interval newInterval) {
+        PriorityQueue<Point> queue = new PriorityQueue<>(Comparator.comparing(p -> p.val));
+        queue.offer(new Point(newInterval.start, 1));
+        queue.offer(new Point(newInterval.end, -1));
+        for (Interval interval : intervals) {
+            queue.offer(new Point(interval.start, 1));
+            queue.offer(new Point(interval.end, -1));
+        }
+        return queue;
+    }
+    
 }
 
 
 
+
 /*
 O(n) time, O(1) space
 Thoughts: