package leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

/**
 * https://leetcode.com/problems/online-election/
 */
public class Problem911 {
    private static class TopVotedCandidate {
        private final Map<Integer /*time*/, Integer /*person*/> timePerson = new HashMap<>();
        private final TreeSet<Integer> timeSet = new TreeSet<>();

        public TopVotedCandidate(int[] persons, int[] times) {
            int maxPerson = 0;
            Map<Integer /*person*/, Integer /*count*/> personCount = new HashMap<>();
            for (int i = 0; i < times.length; i++) {
                timeSet.add(times[i]);
                int count = 0;
                if (!personCount.containsKey(persons[i])) {
                    count = 1;
                } else {
                    count = personCount.get(persons[i]) + 1;
                }
                personCount.put(persons[i], count);
                if (personCount.get(maxPerson) <= count) {
                    maxPerson = persons[i];
                }
                timePerson.put(times[i], maxPerson);
            }
        }

        public int q(int t) {
            Integer time = timeSet.floor(t);
            if (time == null) {
                time = timeSet.first();
            }
            return timePerson.get(time);
        }
    }

    public static void main(String[] args) {
        TopVotedCandidate candidate = new TopVotedCandidate(new int[]{0, 1, 1, 0, 0, 1, 0},
            new int[]{0, 5, 10, 15, 20, 25, 30});
        System.out.println(candidate.q(0)); // 0
        System.out.println(candidate.q(3)); // 0
        System.out.println(candidate.q(12)); // 1
        System.out.println(candidate.q(25)); // 1
        System.out.println(candidate.q(15)); // 0
        System.out.println(candidate.q(24)); // 0
        System.out.println(candidate.q(8)); // 1
        System.out.println(candidate.q(30)); // 0
        System.out.println(candidate.q(35)); // 0
    }
}

@@ -12,16 +12,41 @@
 tcode;%0A%0A
+import java.util.Arrays;%0A
 import j
@@ -88,34 +88,8 @@
 Map;
-%0Aimport java.util.TreeSet;
 %0A%0A/*
@@ -241,239 +241,234 @@
 nal 
-Map%3CInteger /*time*/, Integer /*person*/%3E timePerson = new HashMap%3C%3E();%0A        private final TreeSet%3CInteger%3E timeSet = new TreeSet%3C%3E();%0A%0A        public TopVotedCandidate(int%5B%5D persons, int%5B%5D times) %7B%0A            int maxPerson = 0
+int%5B%5D times;%0A        private final int%5B%5D timePerson;%0A%0A        public TopVotedCandidate(int%5B%5D persons, int%5B%5D times) %7B%0A            this.times = times;%0A            int maxPerson = 0;%0A            timePerson = new int%5Btimes.length%5D
 ;%0A  
@@ -608,47 +608,8 @@
 ) %7B%0A
-                timeSet.add(times%5Bi%5D);%0A
     
@@ -1033,22 +1033,13 @@
 rson
-.put(times
 %5Bi%5D
-,
+ =
  max
@@ -1044,17 +1044,16 @@
 axPerson
-)
 ;%0A      
@@ -1117,165 +1117,48 @@
     
-Integer time = timeSet.floor(t);%0A            if (time == null) %7B%0A                time = timeSet.first();%0A            %7D%0A            return timePerson.get(time
+int index = Arrays.binarySearch(times, t
 );%0A 
@@ -1168,650 +1168,126 @@
     
-%7D%0A
     
-%7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        TopVotedCandidate candidate = new TopVotedCandidate(new int%5B%5D%7B0, 1, 1, 0, 0, 1, 0%7D,%0A            new int%5B%5D%7B0, 5, 10, 15, 20, 25, 30%7D);%0A        System.out.println(candidate.q(0)); // 0%0A        System.out.println(candidate.q(3)); // 0%0A        System.out.println(candidate.q(12)); // 1%0A        System.out.println(candidate.q(25)); // 1%0A        System.out.println(candidate.q(15)); // 0%0A        System.out.println(candidate.q(24)); // 0%0A        System.out.println(candidate.q(8)); // 1%0A        System.out.println(candidate.q(30)); // 0%0A        System.out.println(candidate.q(35)); // 0
+if (index %3C 0) %7B%0A                index = -index - 2;%0A            %7D%0A            return timePerson%5Bindex%5D;%0A        %7D
 %0A   

Solve problem 911