# Raindrop on Sidewalk ### Description > Model raindrops falling on a sidewalk (sidewalk is 1m and raindrops are 1cm). How could we know when the sidewalk is completely wet. Source: OR > you have 1 meter sidewalk, and randomly generate rain, the rain is 1 cm. simulate how many rain drops to cover all the 1 meter \[-0.01\~1]. Source: ## Solution ### TreeSet Approach Not sure why, but seems hard to converge (cover). ```java public class RaindropSidewalk { private TreeSet sidewalk = new TreeSet<>(new Comparator() { @Override public int compare(double[] a, double[] b) { return Double.compare(a[0], b[0]); } }); public void addRainDrop(double center) { double[] range = new double[] {center - 0.5, center + 0.5}; double[] left = sidewalk.floor(range); if (left != null && left[1] > range[0]) { range[0] = left[0]; sidewalk.remove(left); } double[] right = sidewalk.ceiling(range); if (right != null && right[0] < range[1]) { range[1] = right[1]; sidewalk.remove(right); } sidewalk.add(range); } public boolean isCovered() { if (sidewalk.size() == 1) { if (sidewalk.first()[0] <= 0 && sidewalk.first()[1] >= 100) { return true; } } return false; } public void printSideWalk() { System.out.println("--" + sidewalk.size()); for (double[] rain: sidewalk) { System.out.println("::" + Arrays.toString(rain)); } } public void print() { System.out.println("size ::" + sidewalk.size()); } public static void main(String[] args) { Random rand = new Random(); RaindropSidewalk s = new RaindropSidewalk(); int count = 0; for (int rain = 0; rain <= 100; rain++) { s.addRainDrop(rain); s.printSideWalk(); } /* while (!s.isCovered()) { double rain = (double)rand.nextInt(101) + rand.nextDouble(); s.addRainDrop(rain); count++; if (count % 1e5 == 0) { s.print(); } if (count % 1e7 == 0) { s.printSideWalk(); } if (count > 1e9) { break; } } System.out.println("count: " + count); */ } } ``` ### Interval Approach ```java public class RainDrop { static class Interval { double left = 0, right = 0.01; boolean isWet() { return left >= right; } } public static void main(String[] args) { simulateRainDrop(); } public static void simulateRainDrop() { Interval[] sidewalk = new Interval[100]; for (int i = 0; i < 100; i++) { sidewalk[i] = new Interval(); } int cnt = 0, wetCnt = 0; while (wetCnt < 100) { ++cnt; double p = Math.random(); double left = p - 0.005; double right = p + 0.005; if (left >= 0) { int idx = (int) (left / 0.01); if (!sidewalk[idx].isWet()) { double iright = left - idx * 0.01; if (iright < sidewalk[idx].right) { sidewalk[idx].right = iright; if (sidewalk[idx].isWet()) ++wetCnt; } } } if (right <= 1) { int idx = (int) (right / 0.01); if (!sidewalk[idx].isWet()) { double ileft = right - idx * 0.01; if (ileft > sidewalk[idx].left) { sidewalk[idx].left = ileft; if (sidewalk[idx].isWet()) ++wetCnt; } } } } System.out.println(cnt); } } ``` ### Another Interval approach ```java class Main { //start is the distance to 0, end is the distance to 1 //both start and end fall into [0, 1] public class Interval { public double start; public double end; public boolean isCovered; public Interval() { this.start = 0; this.end = 0; this.isCovered = false; } } public class SideWalk { private int curOccupiedCount; public int count; public Interval[] intervals; public SideWalk(int count) { this.curOccupiedCount = 0; this.count = count; this.intervals = new Interval[count]; for (int i = 0; i < this.count; i++) { this.intervals[i] = new Interval(); } } // 1.68..2.68 public void DropRain(double start, double end) { int index = (int) Math.floor(start); if (index >= 0) { if (Math.abs(start - index) < 0.00001) { if (!this.intervals[index].isCovered) { this.curOccupiedCount++; this.intervals[index].isCovered = true; } return; } if (!this.intervals[index].isCovered) { this.intervals[index].end = Math.max(this.intervals[index].end, index + 1 - start); if (this.intervals[index].start + this.intervals[index].end >= 1) { this.intervals[index].isCovered = true; this.curOccupiedCount++; } } } if (index + 1 < this.count) { if (!this.intervals[index + 1].isCovered) { this.intervals[index + 1].start = Math.max(this.intervals[index + 1].start, end - index - 1); if (this.intervals[index + 1].start + this.intervals[index + 1].end >= 1) { this.intervals[index + 1].isCovered = true; this.curOccupiedCount++; } } } } public boolean hasOccupied() { return this.curOccupiedCount == this.count; } } public void SimulateRainDrop() { SideWalk sideWalk = new SideWalk(100); while (!sideWalk.hasOccupied()) { Random random = new Random(); double start = random.nextInt(101) - 1 + random.nextDouble(); double end = start + 1; sideWalk.DropRain(start, end); System.out.println(start + ", " + end); } System.out.println("occupied!"); } public static void main(String[] args) { Main m = new Main(); m.SimulateRainDrop(); } } ``` ## Reference --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://aaronice.gitbook.io/lintcode/company-tag/google/raindrop-on-sidewalk.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.