carfleet medium problem ugly code nice solution

sherxon · Jul 29, 2018 · 1c59415 · 1c59415
1 parent 5d7a38f
commit 1c59415
Show file tree

Hide file tree

Showing 3 changed files with 106 additions and 1 deletion.
diff --git a/src/problems/Medium.txt b/src/problems/Medium.txt
@@ -2801,7 +2801,7 @@ Explanation: Alice's hand can't be rearranged into groups of 4.
  1 <= hand.length <= 10000
  0 <= hand[i] <= 10^9
  1 <= W <= hand.length
- 190)Shifting Letters
+190)Shifting Letters
  We have a string S of lowercase letters, and an integer array shifts.
 
  Call the shift of a letter, the next letter in the alphabet, (wrapping around so that 'z' becomes 'a').
@@ -2825,3 +2825,38 @@ Explanation: Alice's hand can't be rearranged into groups of 4.
 
  1 <= S.length = shifts.length <= 20000
  0 <= shifts[i] <= 10 ^ 9
+191)Car Fleet
+N cars are going to the same destination along a one lane road.  The destination is target miles away.
+
+Each car i has a constant speed speed[i] (in miles per hour), and initial position position[i] miles towards the target along the road.
+
+A car can never pass another car ahead of it, but it can catch up to it, and drive bumper to bumper at the same speed.
+
+The distance between these two cars is ignored - they are assumed to have the same position.
+
+A car fleet is some non-empty set of cars driving at the same position and same speed.  Note that a single car is also a car fleet.
+
+If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.
+
+
+How many car fleets will arrive at the destination?
+
+
+
+Example 1:
+
+Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
+Output: 3
+Explanation:
+The cars starting at 10 and 8 become a fleet, meeting each other at 12.
+The car starting at 0 doesn't catch up to any other car, so it is a fleet by itself.
+The cars starting at 5 and 3 become a fleet, meeting each other at 6.
+Note that no other cars meet these fleets before the destination, so the answer is 3.
+
+Note:
+
+0 <= N <= 10 ^ 4
+0 < target <= 10 ^ 6
+0 < speed[i] <= 10 ^ 6
+0 <= position[i] < target
+All initial positions are different.
diff --git a/src/problems/easy/MaximizeDistancetoClosestPerson.java b/src/problems/easy/MaximizeDistancetoClosestPerson.java
@@ -18,6 +18,8 @@ public int maxDistToClosest(int[] a) {
                 count = 0;
             }
         }
+        int r = 0;
+        r += (a[0] < a[1] ? 1 : 0);
         return Math.max(Math.max(result, firstZeros), count);
 
     }

diff --git a/src/problems/medium/CarFleet.java b/src/problems/medium/CarFleet.java
@@ -0,0 +1,68 @@
+package problems.medium;
+
+import java.util.Arrays;
+import java.util.Comparator;
+
+/**
+ * Why Did you create this class? what does it do?
+ */
+public class CarFleet {
+    public static void main(String[] args) {
+        System.out.println(new CarFleet().carFleet(10,
+                new int[] { 0, 2, 4 },
+                new int[] { 2, 3, 1 }));
+        System.out.println(new CarFleet().carFleet(10,
+                new int[] { 6, 8 },
+                new int[] { 3, 2 }));
+
+        System.out.println(new CarFleet().carFleet(12,
+                new int[] { 10, 8, 0, 5, 3 },
+                new int[] { 2, 4, 1, 1, 3 }));
+    }
+
+    public int carFleet(int target, int[] position, int[] speed) {
+
+        if (speed == null || speed.length == 0)
+            return 0;
+        if (speed.length == 1)
+            return 1;
+
+        int r = 0;
+        Pair[] pairs = new Pair[speed.length];
+
+        for (int i = 0; i < speed.length; i++) {
+            pairs[i] = new Pair(position[i], speed[i]);
+        }
+        Arrays.sort(pairs, Comparator.comparingInt(a -> a.pos));
+        double[] a = new double[pairs.length];
+        for (int i = pairs.length - 1; i >= 0; i--) {
+            a[i] = (target - pairs[i].pos * 1.0) / pairs[i].speed;
+        }
+        boolean infleet = false;
+        for (int i = a.length - 1; i > 0; i--) {
+            if (a[i] < a[i - 1]) {
+                r += infleet ? 0 : 1;
+                infleet = false;
+                continue;
+            }
+            if (!infleet) {
+                r++;
+                infleet = true;
+            }
+            a[i - 1] = Math.max(a[i - 1], a[i]);
+        }
+
+        r += (a[0] > a[1] ? 1 : 0);
+        return r;
+    }
+
+    class Pair {
+        int pos;
+        int speed;
+
+        Pair(int p, int s) {
+            pos = p;
+            speed = s;
+        }
+    }
+}