c*********m
发帖数: 43 | 1 一堆racer，每个racer有出发时间和到达时间，计算每个racer的score，规则如下
：score ＝ 所有出发比自己晚但是到达比自己早的racer数量之和，（所有的出发时间
和到达时间没有重复的）要求时间复杂度o(nlgn).
这题什么思路呢？interval tree? nlgn的想法想不到啊。 |
y**k
发帖数: 222 | |
r*******e
发帖数: 7583 | 3 到达时间放进order-statistic tree
然后根据出发从早到晚，依次查询到达时间的rank，也就是score
同时每查询一个，就从tree里删掉一个
每次查询和删除都是O(lgn)
间
【在 c*********m 的大作中提到】
: 一堆racer，每个racer有出发时间和到达时间，计算每个racer的score，规则如下
: ：score ＝ 所有出发比自己晚但是到达比自己早的racer数量之和，（所有的出发时间
: 和到达时间没有重复的）要求时间复杂度o(nlgn).
: 这题什么思路呢？interval tree? nlgn的想法想不到啊。
|
f*****e
发帖数: 2992 | 4 这题我发过，n1=|arrival < this arival|
n2=|start < this start|
n1 - n2
【在 y**k 的大作中提到】
: 排序加点数学。
|
c*********m
发帖数: 43 | 5 你能说得详细点吗？不太明白，谢谢。
【在 f*****e 的大作中提到】
: 这题我发过，n1=|arrival < this arival|
: n2=|start < this start|
: n1 - n2
|
c**s
发帖数: 159 | |
B********t
发帖数: 147 | 7 这不是类似merge interval么？ 难道我理解错题意了？
BTW: 我申他家 上来就让我写个tail命令的实现 |
s*******r
发帖数: 2697 | 8 这个思路好 不用什么线段树了
【在 f*****e 的大作中提到】
: 这题我发过，n1=|arrival < this arival|
: n2=|start < this start|
: n1 - n2
|
c*********m
发帖数: 43 | 9 你能详细说下嘛？没太明白这个思路啥意思，真写代码肯定没法用线段树啦啊，谢谢!
【在 s*******r 的大作中提到】
: 这个思路好 不用什么线段树了
|
m*******8
发帖数: 539 | 10 可是n2里的racer不见得都在n1里吧，也有出发早但到的晚的啊
【在 f*****e 的大作中提到】
: 这题我发过，n1=|arrival < this arival|
: n2=|start < this start|
: n1 - n2
|
|
|
t*******3
发帖数: 734 | |
w***y
发帖数: 6251 | 12 rocket fuel?
【在 t*******3 的大作中提到】
: 什么是rf？
|
b*****n
发帖数: 143 | 13 My C++ implementation:
#include
#include
#include |
k*******2
发帖数: 84 | 14 我code test也是tail命令，不过我第一轮phone interview已经挂了。他家的题目不简
单，大家加油！ |
f*****e
发帖数: 210 | 15 mark
间
【在 c*********m 的大作中提到】
: 一堆racer，每个racer有出发时间和到达时间，计算每个racer的score，规则如下
: ：score ＝ 所有出发比自己晚但是到达比自己早的racer数量之和，（所有的出发时间
: 和到达时间没有重复的）要求时间复杂度o(nlgn).
: 这题什么思路呢？interval tree? nlgn的想法想不到啊。
|
h********0
发帖数: 74 | 16 --- score ＝ 所有出发比自己晚但是到达比自己早的racer数量之和, ---
是那些racer的个数, 不是他们的score 之和, 对不?
my idea is:
1 create a map and listA that makes the start
time ordered ,
2 travel the startTime, from big to small, and create a listB to store the
endTime in order
2.1 to the first Race whose startTime is biggest, insert his endTime in
the listB, the position is 0, so the score is 0
2.2 to every Racer, binary search his endTime in listB, the position is
his score.
code:
public boolean calScore(ArrayList racers){
//pre-check
if(racers == null || racers.size() == 0)
return false;
HashMap map = new HashMap();
List startTimeList = new ArrayList();
for(Racer racer : racers){
map.put(racer.getStartTime(), racer);
startTimeList.add(racer.getStartTime());
}
Collections.sort(startTimeList);
List endTimeList = new ArrayList();
Racer racer;
for(int i=startTimeList.size() - 1; i>= 0; i--){
racer = map.get(startTimeList.get(i));
racer.setScore(getPosition(endTimeList, racer.getEndTime()));
}
return true;
}
private int getPosition(List endTimes, int x){
if(endTimes == null || endTimes.size() == 0 ){
endTimes.add(0, x);
return 0;
}
int lower = 0, higher = endTimes.size() - 1, middle;
while(lower <= higher){
middle = lower + ((higher - lower) >> 1);
if(x <= endTimes.get(middle) )
higher = middle -1;
else
lower = middle + 1;
}
endTimes.add(lower, x);
return lower;
}
【在 f*****e 的大作中提到】
: mark
:
: 间
|
x*****0
发帖数: 452 | |
c*********m
发帖数: 43 | 18 你这个代码不是nlgn啦，因为distance函数是O(n)时间的，map的iterator类型不是
Random Access Iterator的，思路是很清晰啦
【在 b*****n 的大作中提到】
: My C++ implementation:
: #include
: #include
: #include
|
b***e
发帖数: 1419 | 19 1. Sort intervals (s_i, e_i) such that s_0 < s_1 < ... < s_n. This is O(n*
log(n)).
2. Compute c_i, where c_i = number j's where e_j < e_i. This can be O(n*log
(n)) by sorting e_i.
3. Now traverse (s_i, e_i) from 0 to n:
sorted = [];
for (i = 0; i < n; i++) {
insert_position = binary_insert e_i into sorted;
a_i = c_i - insert_position;
}
This step takes O(n*log(n)) as well.
The result is recorded in a_i.
间
【在 c*********m 的大作中提到】
: 一堆racer，每个racer有出发时间和到达时间，计算每个racer的score，规则如下
: ：score ＝ 所有出发比自己晚但是到达比自己早的racer数量之和，（所有的出发时间
: 和到达时间没有重复的）要求时间复杂度o(nlgn).
: 这题什么思路呢？interval tree? nlgn的想法想不到啊。
|
b*****n
发帖数: 618 | 20 请教一下insert to list 怎样才能O(1)? |
|
|
f*********m
发帖数: 726 | 21 "binary_insert e_i into sorted"是在第一步sorted的Interval中insert吗？
好像不对啊。
log
【在 b***e 的大作中提到】
: 1. Sort intervals (s_i, e_i) such that s_0 < s_1 < ... < s_n. This is O(n*
: log(n)).
: 2. Compute c_i, where c_i = number j's where e_j < e_i. This can be O(n*log
: (n)) by sorting e_i.
: 3. Now traverse (s_i, e_i) from 0 to n:
: sorted = [];
: for (i = 0; i < n; i++) {
: insert_position = binary_insert e_i into sorted;
: a_i = c_i - insert_position;
: }
|
b***e
发帖数: 1419 | 22 No. In Step 3, note that I initiated "sorted" as an empty array.
【在 f*********m 的大作中提到】
: "binary_insert e_i into sorted"是在第一步sorted的Interval中insert吗？
: 好像不对啊。
:
: log
|
s*******e
发帖数: 1630 | 23 请问这个sorted是按什么sort的？
【在 b***e 的大作中提到】
: No. In Step 3, note that I initiated "sorted" as an empty array.
|
h********g
发帖数: 496 | 24
间
rf是什么公司？
【在 c*********m 的大作中提到】
: 一堆racer，每个racer有出发时间和到达时间，计算每个racer的score，规则如下
: ：score ＝ 所有出发比自己晚但是到达比自己早的racer数量之和，（所有的出发时间
: 和到达时间没有重复的）要求时间复杂度o(nlgn).
: 这题什么思路呢？interval tree? nlgn的想法想不到啊。
|
f*********m
发帖数: 726 | 25 你是说把e_i一个一个放到空的sorted array，然后看每个e_i在sorted array中的位置？
那么什么时候用到s_i的信息呢？
谢谢。
【在 b***e 的大作中提到】
: No. In Step 3, note that I initiated "sorted" as an empty array.
|
b***e
发帖数: 1419 | 26 That was used in the first step...
置？
【在 f*********m 的大作中提到】
: 你是说把e_i一个一个放到空的sorted array，然后看每个e_i在sorted array中的位置？
: 那么什么时候用到s_i的信息呢？
: 谢谢。
|
p*****2
发帖数: 21240 | 27
tail命令是傻题呀？
【在 k*******2 的大作中提到】
: 我code test也是tail命令，不过我第一轮phone interview已经挂了。他家的题目不简
: 单，大家加油！
|
r*******e
发帖数: 7583 | 28 实现unix command "tail"
不简
【在 p*****2 的大作中提到】
:
: tail命令是傻题呀？
|
p*****2
发帖数: 21240 | 29
实现到啥程度呀？
【在 r*******e 的大作中提到】
: 实现unix command "tail"
:
: 不简
|
f*********m
发帖数: 726 | 30 哦，了解了。
最后一步把e_i插入sorted array,指的是把在第一步中根据s_i排好的e_i按顺序插入到
sorted array，插入一个就看其插入的位置，而不是等到都插入完了再看每个e_i的位
置，对吧？
【在 b***e 的大作中提到】
: That was used in the first step...
:
: 置？
|
|
|
h********0
发帖数: 74 | 31 correction:
The operation in listB is not O(logn). We can use a BST to store the endTime
relative position.
class TreeNode{
endTime; //example "201305061323" :) timestamp is better
count; //there are 2 "201305061323", count=2;
leftNodeSum; //the sum of left child's count
TreeNode left;
TreeNode right;
}
int getPosition(TreeNode root, int endTime){
if(endTime == root.endTime)
return root.leftNodeSum;
if(endTime < root.endTime)
return getPosition(root.left, endTime);
else
return root.leftNodeSum + root.count + getPosition(root.right, endTime);
}
note: keeping this BST balanced is not easy coding in interview.
【在 h********0 的大作中提到】
: --- score ＝ 所有出发比自己晚但是到达比自己早的racer数量之和, ---
: 是那些racer的个数, 不是他们的score 之和, 对不?
: my idea is:
: 1 create a map and listA that makes the start
: time ordered ,
: 2 travel the startTime, from big to small, and create a listB to store the
: endTime in order
: 2.1 to the first Race whose startTime is biggest, insert his endTime in
: the listB, the position is 0, so the score is 0
: 2.2 to every Racer, binary search his endTime in listB, the position is
|
G****A
发帖数: 4160 | 32 我也觉得是merge interval.
【在 B********t 的大作中提到】
: 这不是类似merge interval么？ 难道我理解错题意了？
: BTW: 我申他家 上来就让我写个tail命令的实现
|
b***e
发帖数: 1419 | 33 Yes. That's the trick of this problem.
【在 f*********m 的大作中提到】
: 哦，了解了。
: 最后一步把e_i插入sorted array,指的是把在第一步中根据s_i排好的e_i按顺序插入到
: sorted array，插入一个就看其插入的位置，而不是等到都插入完了再看每个e_i的位
: 置，对吧？
|
y**k
发帖数: 222 | 34 赞思路清晰。最后一步似需修正。
【在 b***e 的大作中提到】
: Yes. That's the trick of this problem.
|
b***e
发帖数: 1419 | 35 愿闻其详。
【在 y**k 的大作中提到】
: 赞思路清晰。最后一步似需修正。
|
p*****2
发帖数: 21240 | 36 感觉可以build一个tree，子树的数目就是score |
l**********g
发帖数: 426 | 37 endTimes.add(lower, x);
----this is an O(n) operation ?
【在 h********0 的大作中提到】
: --- score ＝ 所有出发比自己晚但是到达比自己早的racer数量之和, ---
: 是那些racer的个数, 不是他们的score 之和, 对不?
: my idea is:
: 1 create a map and listA that makes the start
: time ordered ,
: 2 travel the startTime, from big to small, and create a listB to store the
: endTime in order
: 2.1 to the first Race whose startTime is biggest, insert his endTime in
: the listB, the position is 0, so the score is 0
: 2.2 to every Racer, binary search his endTime in listB, the position is
|
s******n
发帖数: 226 | 38 Insert into BST and get score.
This is runnable code.
class node{
int val;
int below;
node left;
node right;
node(int val){this.val = val; left = right = null; below = 0;}
}
class Tree{
node root;
Tree(){root = null;}
int insert(int val){
node N = root;
if(N == null){
root = new node(val);
return 0;
}
int score = 0;
node par = null;
while(N!=null){
if(val <= N.val){
N.below++;
par = N;
N = N.left;
}else{
N.below++;
if(N.left == null) score++;
else score += 2+N.left.below;
par = N;
N = N.right;
}
}
if(val <= par.val){
node nd = new node(val);
par.left = nd;
return score;
}
else{
node nd = new node(val);
par.right = nd;
return score;
}
}
} |
p*****2
发帖数: 21240 | 39
log
sorted = [];
for (i = 0; i < n; i++) {
insert_position = binary_insert e_i into sorted;
a_i = c_i - insert_position;
}
This step takes O(n*log(n)) as well.
这个insert为什么是logn呢？什么数据结构？
【在 b***e 的大作中提到】
: 1. Sort intervals (s_i, e_i) such that s_0 < s_1 < ... < s_n. This is O(n*
: log(n)).
: 2. Compute c_i, where c_i = number j's where e_j < e_i. This can be O(n*log
: (n)) by sorting e_i.
: 3. Now traverse (s_i, e_i) from 0 to n:
: sorted = [];
: for (i = 0; i < n; i++) {
: insert_position = binary_insert e_i into sorted;
: a_i = c_i - insert_position;
: }
|
p*****2
发帖数: 21240 | 40
怎么没看到start－end？
【在 s******n 的大作中提到】
: Insert into BST and get score.
: This is runnable code.
: class node{
: int val;
: int below;
: node left;
: node right;
: node(int val){this.val = val; left = right = null; below = 0;}
: }
: class Tree{
|
|
|
p*****2
发帖数: 21240 | 41
有现成的order-statistic tree可用吗？感觉也不好写呀。
【在 r*******e 的大作中提到】
: 到达时间放进order-statistic tree
: 然后根据出发从早到晚，依次查询到达时间的rank，也就是score
: 同时每查询一个，就从tree里删掉一个
: 每次查询和删除都是O(lgn)
:
: 间
|
r*********n
发帖数: 4553 | 42 这到题难道不是longest increasing subsequence的马甲题吗？ |
s******n
发帖数: 226 | 43 Complete code:
import java.util.*;
import java.lang.Math.*;
// Customized Tree for sorting ending times and count how many ending times
are earlier than inserted one to compute the racer's score.
// Insertion is O(nlgn)
class node{
int val;
int below;
node left;
node right;
node(int val){this.val = val; left = right = null; below = 0;}
}
class Tree{
node root;
Tree(){root = null;}
int insert(int val){
node N = root;
if(N == null){
root = new node(val);
return 0;
}
int score = 0;
node par = null;
while(N!=null){
if(val <= N.val){
N.below++;
par = N;
N = N.left;
}else{
N.below++;
if(N.left == null) score++;
else score += 2+N.left.below;
par = N;
N = N.right;
}
}
if(val <= par.val){
node nd = new node(val);
par.left = nd;
return score;
}
else{
node nd = new node(val);
par.right = nd;
return score;
}
}
}
// racer class, to store the start and ending time for each racer
class racer{
double start;
double end;
racer(double a, double b){
start = a; end = b;
}
// This function is helper function to create racer, since if start
== end is not allowed.
static racer genRacer(double a, double b){
if(a < b) return new racer(a,b);
else if(a > b) return new racer(b,a);
return null;
}
// Comparison function, used in racer array sorting function
accoring to starting time
static boolean less(racer a, racer b){
return (a.start <= b.start);
}
// Quick Sort for racer class, using comparison function above
static int partition(racer[]a , int left, int right){
int n = a.length;
if(right=n) return -1;
racer p = a[left];
int l = left-1;
int r = right +1;
while(l<=r){
while(++l
while((--r)>l && less(p, a[r]));
if(l>r) break;
double tmp = a[l].start;
a[l].start = a[r].start;
a[r].start = tmp;
tmp = a[l].end;
a[l].end = a[r].end;
a[r].end = tmp;
}
double tmp = a[left].start;
a[left].start = a[r].start;
a[r].start = tmp;
tmp = a[left].end;
a[left].end = a[r].end;
a[r].end = tmp;
return r;
}
static void subqsort(racer[] a, int left, int right){
int p = partition(a,left, right);
if(p==-1) return;
// System.out.println("Partition at "+p);
subqsort(a,left,p-1);
subqsort(a,p+1,right);
}
public static racer[] sort(racer[] arr){
int N = arr.length;
if(N<=0) return null;
subqsort(arr,0,arr.length-1);
return arr;
}
// Print racer's time virtually
public static void printRace(racer[] arr){
int tt=0;
for(racer i : arr){
System.out.print("#"+(tt++)+":");
int start = (int)(i.start*100);
int end = (int)(i.end*100);
for(int j =0; j
System.out.print("[");
for(int j =0; j
System.out.print("]");
System.out.println();
}
}
}
// class to run this algorithm
class run{
// Generate racers with random starting and ending times
static racer[] genRace(int N){
if(N <=0) return null;
racer[] re = new racer[N];
for(int i = 0; i
racer R = racer.genRacer(Math.random(), Math.random());
while(R == null) R = racer.genRacer(Math.random(), Math.random()
);
re[i] = R;
System.out.print("( "+ R.start+", "+R.end+" ), ");
}
System.out.println();
return re;
}
// Main function
public static void main(String[] args){
int N = 20;
racer[] race = genRace(N);
race = racer.sort(race);
racer.printRace(race);
Tree T = new Tree();
// Insert into Tree and print out score
for(int i = N-1; i>=0; i--){
System.out.println("#"+i+" score is "+ T.insert((int)(race[i].
end*100)));
}
}
}
【在 p*****2 的大作中提到】
:
: 有现成的order-statistic tree可用吗？感觉也不好写呀。
|
p*****2
发帖数: 21240 | 44
times
你这个tree是balanced的吗？
【在 s******n 的大作中提到】
: Complete code:
: import java.util.*;
: import java.lang.Math.*;
: // Customized Tree for sorting ending times and count how many ending times
: are earlier than inserted one to compute the racer's score.
: // Insertion is O(nlgn)
: class node{
: int val;
: int below;
: node left;
|
s******n
发帖数: 226 | 45 OK averg case
【在 p*****2 的大作中提到】
:
: times
: 你这个tree是balanced的吗？
|
p*****2
发帖数: 21240 | 46
你这个有过他们的test吗？不知道是否能应付一些极端的test case
【在 s******n 的大作中提到】
: OK averg case
|
s******n
发帖数: 226 | 47 我不知道RF是哪.就是昨天看到这道题，就写了一下。
【在 p*****2 的大作中提到】
:
: 你这个有过他们的test吗？不知道是否能应付一些极端的test case
|
p*****2
发帖数: 21240 | 48
这个貌似也不对吧？这题感觉不简单呀。尤其是要过OJ。
【在 f*****e 的大作中提到】
: 这题我发过，n1=|arrival < this arival|
: n2=|start < this start|
: n1 - n2
|
t*q
发帖数: 104 | 49 binary insert为啥是log(n)啊，如何implement？
log
【在 b***e 的大作中提到】
: 1. Sort intervals (s_i, e_i) such that s_0 < s_1 < ... < s_n. This is O(n*
: log(n)).
: 2. Compute c_i, where c_i = number j's where e_j < e_i. This can be O(n*log
: (n)) by sorting e_i.
: 3. Now traverse (s_i, e_i) from 0 to n:
: sorted = [];
: for (i = 0; i < n; i++) {
: insert_position = binary_insert e_i into sorted;
: a_i = c_i - insert_position;
: }
|
t*q
发帖数: 104 | 50 OJ在什么地方？
【在 p*****2 的大作中提到】
:
: 这个貌似也不对吧？这题感觉不简单呀。尤其是要过OJ。
|
|
|
p*****2
发帖数: 21240 | 51
应该是RF会提供。
这题到现在也没有一个好的说法。算法大家分析的差不多。不过实现不好搞呀。不知道
有没有什么更好的办法。
【在 t*q 的大作中提到】
: OJ在什么地方？
|
t*q
发帖数: 104 | 52 就是求逆序的加强版啊
【在 p*****2 的大作中提到】
:
: 应该是RF会提供。
: 这题到现在也没有一个好的说法。算法大家分析的差不多。不过实现不好搞呀。不知道
: 有没有什么更好的办法。
|
p*****2
发帖数: 21240 | 53
什么是求逆序呀？
【在 t*q 的大作中提到】
: 就是求逆序的加强版啊
|
t*q
发帖数: 104 | |
p*****2
发帖数: 21240 | |
i******s
发帖数: 301 | 56 import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.TreeSet;
public class Solution {
public static class Racer {
public int start;
public int end;
public int score;
public Racer(int start, int end, int score) {
this.start = start;
this.end = end;
this.score = score;
}
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.
in));
String line;
List racers = new ArrayList();
while((line = in.readLine())!=null){
String[] data = line.split(" ");
racers.add( new Racer(Integer.parseInt(data[0]), Integer.
parseInt(data[1]), 0));
}
List sortByStart = new ArrayList(racers);
Collections.sort(sortByStart, new Comparator() {
public int compare(Racer a, Racer b) {
return a.start - b.start;
}
});
int[] sortByEnd = new int[racers.size()];
for (int i=0; i < racers.size(); ++i) {
Racer racer = racers.get(i);
sortByEnd[i] = racer.end;
}
Arrays.sort(sortByEnd);
TreeSet processedRacer = new TreeSet(new Comparator<
Racer>() {
public int compare(Racer a, Racer b) {
return a.end - b.end;
}
});
for (Racer racer : sortByStart) {
int a = Arrays.binarySearch(sortByEnd, racer.end);
int b = processedRacer.size() - processedRacer.tailSet(racer).
size();
processedRacer.add(racer);
racer.score = a - b;
}
for (Racer racer : racers) {
System.out.println(racer.score);
}
}
}
间
【在 c*********m 的大作中提到】
: 一堆racer，每个racer有出发时间和到达时间，计算每个racer的score，规则如下
: ：score ＝ 所有出发比自己晚但是到达比自己早的racer数量之和，（所有的出发时间
: 和到达时间没有重复的）要求时间复杂度o(nlgn).
: 这题什么思路呢？interval tree? nlgn的想法想不到啊。
|
b***e
发帖数: 1419 | 57 (Balanced) Tree that records the size of each subtree in the subroot.
【在 p*****2 的大作中提到】
:
: 哇。太牛了。膜拜一下了。多谢。
|
x*********w
发帖数: 533 | 58
展开说说？？
【在 t*q 的大作中提到】
: 就是求逆序的加强版啊
|
p*****2
发帖数: 21240 | 59
balanced tree是可以。不过自己写一个还是太麻烦了吧。我是从来没有写过。
【在 b***e 的大作中提到】
: (Balanced) Tree that records the size of each subtree in the subroot.
|
p*****2
发帖数: 21240 | 60
大牛自己好好体会一下吧。呆鸭子太牛了。
【在 x*********w 的大作中提到】
:
: 展开说说？？
|
|
|
b***e
发帖数: 1419 | 61 O(n^2) is trivial. Just to provide a means to O(n*log(n)), which I don't
see other posts providing clearly. Not interested in implementing any sort
of algorithms. The math's interesting, the coding's tedious.
【在 p*****2 的大作中提到】
:
: 大牛自己好好体会一下吧。呆鸭子太牛了。
|
p*****2
发帖数: 21240 | 62
sort
嗯。算法是不错的。
【在 b***e 的大作中提到】
: O(n^2) is trivial. Just to provide a means to O(n*log(n)), which I don't
: see other posts providing clearly. Not interested in implementing any sort
: of algorithms. The math's interesting, the coding's tedious.
|
b***e
发帖数: 1419 | 63 So much for Mr. Odersky and now coffeescript + node.js?
【在 p*****2 的大作中提到】
:
: sort
: 嗯。算法是不错的。
|
p*****2
发帖数: 21240 | 64
前几天玩了玩。最近回Java了。感觉做题还是Java用的踏实一些。作项目的话node挺好
。
【在 b***e 的大作中提到】
: So much for Mr. Odersky and now coffeescript + node.js?
|
d****n
发帖数: 233 | 65 Post a O(NlogN) solution.
class Racer
{
public Racer(int id, int start, int end)
{
Id = id;
Start = start;
End = end;
StartRank = 0;
Score = 0;
}
public int Id { get; set; }
public int Start { get; set; }
public int End { get; set; }
public int Score { get; set; }
public int StartRank { get; set; }
}
void RankRacers(Racer[] racers)
{
Array.Sort(racers, (a, b) => a.Start - b.Start);
for (int i = 0; i < racers.Length; ++i)
{
racers[i].StartRank = i;
}
Array.Sort(racers, (a, b) => a.End - b.End);
List StartRanks = new List();
for (int i = 0; i < racers.Length; ++i)
{
// the score is the number of processed racers(ended earlier)
// whose StartRank is higher than current racer.
racers[i].Score = BinarySearchInsert(StartRanks, racers[i].StartRank);
}
Array.Sort(racers, (a, b) => a.Score - b.Score);
}
int BinarySearchInsert(List processedRanks, int startRank)
{
int index = processedRanks.BinarySearch(startRank);
index = (index < 0) ? ~index : index;
int score = processedRanks.Count - index;
processedRanks.Insert(index, startRank);
return score;
}
Hope this helps.
【在 p*****2 的大作中提到】
:
: 前几天玩了玩。最近回Java了。感觉做题还是Java用的踏实一些。作项目的话node挺好
: 。
|
t*q
发帖数: 104 | 66 汗，大家互相吹捧啊
【在 p*****2 的大作中提到】
:
: 前几天玩了玩。最近回Java了。感觉做题还是Java用的踏实一些。作项目的话node挺好
: 。
|
x*********w
发帖数: 533 | 67
太厉害了，是怎么想到的
【在 t*q 的大作中提到】
: 汗，大家互相吹捧啊
|
p*****2
发帖数: 21240 | 68
感觉做过800题也不一定能想到呀。
【在 x*********w 的大作中提到】
:
: 太厉害了，是怎么想到的
|
g***9
发帖数: 159 | |
w****x
发帖数: 2483 | 70 public class RacerScore
{
static public class Segment
{
int id = -1;
int beg = 0;
int end = 0;
Segment(int i, int b, int e)
{
id = i;
beg = b;
end = e;
}
}
static public class comp implements Comparator
{
public int compare(Segment s1, Segment s2)
{
return s1.beg - s2.beg;
}
}
static public void getScores(Segment[] segs, int b, int e, HashMap<
Integer, Integer> mp, Segment[] tmp)
{
if (b >= e) // >= not <
return;
int mid = (b + e)/2;
getScores(segs, b, mid, mp, tmp);
getScores(segs, mid + 1, e, mp, tmp);
int lftIter = b;
int rgtIter = mid + 1;
int iter = 0;
while (lftIter <= mid || rgtIter <= e)
{
if (lftIter <= mid && (rgtIter > e || segs[lftIter].end < segs[
rgtIter].end))
{
if (!mp.containsKey(segs[lftIter].id))
mp.put(segs[lftIter].id, 0);
mp.put(segs[lftIter].id, mp.get(segs[lftIter].id) + rgtIter
- mid - 1);
tmp[iter++] = segs[lftIter++];
}
else
{
tmp[iter++] = segs[rgtIter++];
}
}
for (int i = 0; i <= e - b; i++)
segs[b + i] = tmp[i];
}
static public void printScore(Segment[] segs)
{
if (null == segs)
return;
Arrays.sort(segs, new comp());
HashMap map = new HashMap();
Segment[] tmp = new Segment[segs.length];
getScores(segs, 0, segs.length-1, map, tmp);
Iterator iter = map.keySet().iterator();
while (iter.hasNext())
{
int id = iter.next();
int num = map.get(id);
System.out.println(id + " " + num);
}
}
public static void main(String[] strs)
{
Segment[] segs = new Segment[10];
segs[0] = new Segment(0, 0, 4);
segs[1] = new Segment(1, 1, 3);
segs[2] = new Segment(2, 2, 3);
segs[3] = new Segment(3, 3, 12);
segs[4] = new Segment(4, 4, 6);
segs[5] = new Segment(5, 9, 14);
segs[6] = new Segment(6, 10, 44);
segs[7] = new Segment(7, 12, 32);
segs[8] = new Segment(8, 4, 7);
segs[9] = new Segment(9, 16, 24);
printScore(segs);
}
} |
|
|
d****n
发帖数: 233 | 71 Added this to my blog at: http://codeanytime.blogspot.com/2013/05/score-of-racers.html
【在 d****n 的大作中提到】
: Post a O(NlogN) solution.
: class Racer
: {
: public Racer(int id, int start, int end)
: {
: Id = id;
: Start = start;
: End = end;
: StartRank = 0;
: Score = 0;
|
r*********n
发帖数: 4553 | 72 the most natural method is to first sort the data w.r.t. starting time and
iterate backwards while building a balanced binary search tree to access
rank.
if implemented in c++, the dilemma is that the stl map/set do not provide
rank functionality, you will have to use a combination of lower_bound and
distance to get rank, where distance runs in linear time since map/set do
not have random iterator.
to achieve O(nlogn), you will have to implement balanced bst yourself which
is more difficult than the problem itself.
another approach is to modify the inversion count algorithm:
http://www.geeksforgeeks.org/counting-inversions/
suppose you save data in tuple arr[N] with (start, end, score
). first sort arr w.r.t. start, then use modified merge sort from above
where comparison is w.r.t. end, during the merge step, update score
accordingly. |
H****r
发帖数: 2801 | 73 这题有oj? 求链接，这两天晚上想玩玩这个题哈
【在 p*****2 的大作中提到】
:
: 感觉做过800题也不一定能想到呀。
|
p*****2
发帖数: 21240 | |
H****r
发帖数: 2801 | 75 rf 根本不尔我啊 ... :((
有其他的oj么？
【在 p*****2 的大作中提到】
: 你去申请就会得到连接了
|
