Simulate rain in 1 meter side walk - Google Interview

http://www.1point3acres.com/bbs/thread-176388-1-1.html
you have 1 meter walkroad, and randomly generate rain, the rain is 1 cm. simulate how many rain drops to cover all the 1 meter [-0.01~1].
用merge intervals

1.         static class Interval {
2.                 double left = 0, right = 0.01;
3. 
   
4.                 boolean isWet() {
5.                         return left >= right;
6.                 }. 1point 3acres 璁哄潧
7.         }
8. 
   
9.         public static void main(String[] args) {
10.                 simulateRainDrop();
11.         }
12.         
13.         public static void simulateRainDrop() {
14. . visit 1point3acres.com for more.
15.                 Interval[] sidewalk = new Interval[100];
16.                 for (int i = 0; i < 100; i++) {. 1point 3acres 璁哄潧
17.                         sidewalk[i] = new Interval();
18.                 }
19.                 int cnt = 0, wetCnt = 0;
20.                 while (wetCnt < 100) {. 鍥磋鎴戜滑@1point 3 acres
21.                         ++cnt;
22.                         double p = Math.random();
23.                         double left = p - 0.005;
24.                         double right = p + 0.005;
25.                         if (left >= 0) {
26.                                 int idx = (int) (left / 0.01);
27.                                 if (!sidewalk[idx].isWet()) {
28.                                         double iright = left - idx * 0.01;
29.                                         if (iright < sidewalk[idx].right) {. 1point 3acres 璁哄潧
30.                                                 sidewalk[idx].right = iright;
31.                                                 if (sidewalk[idx].isWet())
32.                                                         ++wetCnt;
33.                                         }. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
34.                                 }. from: 1point3acres.com/bbs 
35.                         }
36.                         if (right <= 1) {
37.                                 int idx = (int) (right / 0.01);
38.                                 if (!sidewalk[idx].isWet()) {
39.                                         double ileft = right - idx * 0.01;
40.                                         if (ileft > sidewalk[idx].left) {
41.                                                 sidewalk[idx].left = ileft;
42.                                                 if (sidewalk[idx].isWet())
43.                                                         ++wetCnt;
44.                                         }.鏈枃鍘熷垱鑷�1point3acres璁哄潧
45.                                 }
46.                         }
47.                 }
48.                 System.out.println(cnt);. more info on 1point3acres.com
49.         }
50. }

定义一个 struct interv {     double left=0, right=0.01;     bool isWet() {         return left>=right;     } }; 就好了，然后生成0,1之间的一个均匀分布，模拟每个雨滴看落到哪个interval里，直. Waral 鍗氬鏈夋洿澶氭枃绔�, 到100个都打湿。 vector<interv> sidewalk(100,interv()); int cnt=0, wetCnt=0, idx; while(wetCnt<100) {             ++cnt;             double p= (double)(rand())/RAND_MAX;             double left=p-0.005;             double right=p+0.005;             if(left>=0) {. 1point3acres.com/bbs                 idx=left/0.01;                 if(!sidewalk[idx].isWet()) {                     iright=left-idx*0.01;                     if (iright<sidewalk[idx].right) {                         sidewalk[idx].right=iright;                         if(sidewalk[idx].wet()) ++wetCnt;                     }                 }             }             if(right<=1) {. 鍥磋鎴戜滑@1point 3 acres                 idx=right/0.01;                 if(!sidewalk[idx].wet()) {                     ileft=right-idx*0.01;. From 1point 3acres bbs                     if (ileft>sidewalk[idx].left) {                         sidewalk[idx].left=ileft;                         if(sidewalk[idx].isWet()) ++wetCnt;                     }                 }             }         }

https://moonstonelin.wordpress.com/2016/05/26/simulate-rain-in-1-meter-side-walk/

    public void SimulateRainDrop()

    {

        SideWalk sideWalk = new SideWalk(100);

        while (!sideWalk.HasOccupied())

        {

            Random random = new Random();

            double start = random.Next(101) - 1 + random.NextDouble();

            double end = start + 1;

            sideWalk.DropRain(start, end);

            Console.Write(start);

            Console.Write(" , ");

            Console.Write(end);

            Console.Write("\n");

        }

        Console.WriteLine("occupied!");

    }

//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 { get; set; }

    public double End { get; set; }

    public bool IsCovered { get; set; }

    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 bool HasOccupied()

    {

        return this.curOccupiedCount == this.Count;

    }   

}