Rocket fuel OA以及店面

先说OA，这个题目网上都有了。赛车手排序问题。我的做法第4个case过不去。但是还是拿到店面了。废话少说，直接上代码。我按照题目提示用buckets做的，buckets的大小会影响test case的通过率，我反复调也过不了第4个。
Mitbbs上还有大神用别的方法做的。


/* Enter your code here. Read input from STDIN. Print output to STDOUT */
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

class Racer {
        int ID;
        long start;
        long end;
        int score;
        public Racer(int id,long start,long end){
                this.ID = id;
                this.start = start;
                this.end = end;
    }
    public void setscore(int score){
                this.score = score;
        }
        public int getscore(){
                return this.score;
        }
}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        int n = Integer.parseInt(line);
        //arraylist save all racers records
        ArrayList<Racer> A = new ArrayList<Racer>();
        while ((line = br.readLine()) != null) {
           String[] k = line.split(" ");
                   Racer r1 = new Racer(Integer.parseInt(k[0]),Long.parseLong(k[1]),Long.parseLong(k[2]));
                   A.add(r1);
        }
        //sort the A array by start time decending
        Collections.sort(A, new Comparator<Racer>(){
                        public int compare(Racer r1,Racer r2){
                                if(r1.start > r2.start)
                    return -1;
                else
                    return 1;
                        }
                });
        //System.out.println("A size is "+A.size());
        //System.out.println(A.get(0).ID +" "+A.get(0).start );
        //use buckets, split and save all racers' data into buckets, then record the start time range of each bucket
        //sort each bucket by endtime
        ArrayList<ArrayList<Racer>> Buckets = new ArrayList<ArrayList<Racer>>();
        int buck_size = Math.max(1500,(int)Math.sqrt(n));
        HashMap<Integer,Long> map = new HashMap<Integer,Long>();
        int i = 0;
        while(i < A.size()){
            ArrayList<Racer> bucket = new ArrayList<Racer>();
            for(int j=0;j<buck_size&&i<A.size();j++){
                bucket.add(A.get(i));
                i++;
            }
            map.put(Buckets.size(),bucket.get(bucket.size()-1).start);//record each bucket's earliest start time
            //System.out.println("map0123 is "+Buckets.size() + " " + map.get(Buckets.size()));
            //System.out.println("bucket size " + bucket.size());
            //sort this bucket by endtime
            Collections.sort(bucket, new Comparator<Racer>(){
                             public int compare(Racer r1,Racer r2){
                                 if(r1.end < r2.end)
                    return -1;
                 else
                    return 1;
                             }
                      });
            Buckets.add(new ArrayList<Racer>(bucket));
        }

        //travesal all racers and get score
        for(int k=0;k<A.size();k++){
            int score = getscore(A.get(k),Buckets,map);
            A.get(k).setscore(score);
        }
        //sort A by score
        Collections.sort(A, new Comparator<Racer>(){
                        public int compare(Racer r1,Racer r2){
                                return r1.ID - r2.ID;
                        }
                });
        Collections.sort(A, new Comparator<Racer>(){
                        public int compare(Racer r1,Racer r2){
                                return r1.score - r2.score;
                        }
                });
        //output results
        for(Racer r : A){
            System.out.println(r.ID + " " + r.score);
        }

    }

    public static int getscore(Racer r,ArrayList<ArrayList<Racer>> Buckets,HashMap<Integer,Long> map){
        int sum = 0,i = 0;
        for(i=0;i<Buckets.size();i++){
            if(map.get(i) <= r.start)
                break;
            sum += getnum(Buckets.get(i),r.end);
        }
        //process the last bucket
        int count = 0;
        for(Racer p : Buckets.get(i)){
            if(p.end < r.end && p.start > r.start)
                count++;
        }
        /*int q = getnum(Bu

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

long sentance
get all subsets from query vector
ex：
   1 1 0 1 1
   的subsets包括
   1 0 0 0 0
   1 1 0 0 0
.....

   search in hashmap2  


下面是代码，但是我没写完，比较乱，仅作参考
// process data, step 1
HashMap<String,Integer> map = new HashMap<String,Integer>();
int position = 0;
for(i : Ads) // i is single Ad, Ad.ID,  Ad.content
    for(k : i.content){
        if(!map.containsKey(k)){
            map.put(k,position);
            position++;
        }
    }
}



HashMap<Integer,vector[]> map1 = new HashMap<Integer,vector[]>();

for(i : Ads){
    int[] vector = new int[set.size()];
    for(k : i.content){
        vector[map.get(k)] = 1;
    }
    map1.put(i.ID,vector); //ID=1   vector= 1 1 0 0 ....
}

//step 2
int[] Q_vector = new int[set.size()];
for(i : query){
    Q_vector[map.get(i)] = 1;
}


//step 3  build map <vector,List<ID>>

HashMap<vector[],ArrayList<Integer>> map2 = new HashMap<vector[],ArrayList<Integer>>;
for(i : map1.keyValue()){
    if(!map2.containsKey(map1.get(i))
        map2.put(map1.get(i),new ArrayList
}


最后挂了。   

sorry to hear that.   你好，请教个问题哈。最近看面经都提到OA一词，什么是OA啊.我也想做做上面的题目练练，请问怎么在网上去找啊？thank you very much！

chenwoo 发表于 2015-1-12 13:14
sorry to hear that.   你好，请教个问题哈。最近看面经都提到OA一词，什么是OA啊.我也想做做上面的题目练 ...

是Online Assessment

xiaoxin213 发表于 2015-1-12 14:20
是Online Assessment

Thanks, 请问怎么得到OA的机会啊？具体流程怎么做的啊？

我去 答的这么好都挂了 不科学啊