package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

/**
 * https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/
 */
public class Problem497 {
    private static class Solution {
        private final List<int[]> rects = new ArrayList<>();
        private final Random random = new Random();

        public Solution(int[][] rects) {
            for (int i = 0; i < rects.length; i++) {
                long area = area(rects[i]);
                if (area > 0) {
                    this.rects.add(rects[i]);
                }
            }
        }

        public int[] pick() {
            int index = random.nextInt(rects.size());
            int[] rect = rects.get(index);
            int x = random.nextInt(rect[2] - rect[0]) + rect[0];
            int y = random.nextInt(rect[3] - rect[1]) + rect[1];
            return new int[]{x, y};
        }

        private static long area(int[] rect) {
            return (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution(new int[][]{{1, 1, 5, 5}});
        System.out.println(Arrays.toString(solution.pick()));
        System.out.println(Arrays.toString(solution.pick()));
        System.out.println(Arrays.toString(solution.pick()));
    }
}

@@ -33,65 +33,14 @@
 til.
-ArrayList;%0Aimport java.util.Arrays;%0Aimport java.util.List
+Random
 ;%0Aim
@@ -54,22 +54,23 @@
 va.util.
-Random
+TreeMap
 ;%0A%0A/**%0A 
@@ -237,41 +237,49 @@
 nal 
-List%3C
+TreeMap%3CInteger, 
 int%5B%5D%3E 
-rects
+map
  = new 
-ArrayList
+TreeMap
 %3C%3E()
@@ -331,16 +331,42 @@
 andom();
+%0A        private int area;
 %0A%0A      
@@ -395,17 +395,16 @@
 %5D%5B%5D rect
-s
 ) %7B%0A    
@@ -435,17 +435,16 @@
 i %3C rect
-s
 .length;
@@ -471,18 +471,14 @@
     
-long 
 area 
++
 = ar
@@ -480,25 +480,24 @@
 += area(rect
-s
 %5Bi%5D);%0A      
@@ -510,87 +510,31 @@
     
-if (area %3E 0) %7B%0A                    this.rects.add(rects%5Bi%5D);%0A                %7D
+map.put(area, rect%5Bi%5D);
 %0A   
@@ -605,16 +605,29 @@
 int 
-index = 
+key = map.ceilingKey(
 rand
@@ -641,20 +641,17 @@
 Int(
+a
 re
-cts.size()
+a) + 1
 );%0A 
@@ -678,23 +678,19 @@
 t = 
-rects.get(index
+map.get(key
 );%0A 
@@ -740,16 +740,20 @@
  rect%5B0%5D
+ + 1
 ) + rect
@@ -809,16 +809,20 @@
  rect%5B1%5D
+ + 1
 ) + rect
@@ -900,12 +900,11 @@
 tic 
-long
+int
  are
@@ -1008,314 +1008,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Solution solution = new Solution(new int%5B%5D%5B%5D%7B%7B1, 1, 5, 5%7D%7D);%0A        System.out.println(Arrays.toString(solution.pick()));%0A        System.out.println(Arrays.toString(solution.pick()));%0A        System.out.println(Arrays.toString(solution.pick()));%0A    %7D
 %0A%7D%0A

Solve problem 497