# POI 2 Stage 3 Job Scheduling ( Greedy, Math )

http://main.edu.pl/en/archive/oi/2/sze

In the first line of the standard input there is one positive integer not greater then 10000. It is the number of jobs .
In each of the following n lines there is a pair of nonnegative real numbers. The numbers are written in a standard form with a decimal point and six digits after the point. The numbers are separated by a single space. It is the pair of coefficients ai and bi determining the dependence of the execution time of the corresponding -th job upon the time it starts.

O( N lg N ) / O( N )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN =  10000;

int N;
pair< double, double > job[ MAXN ];

int ord[ MAXN ];

bool cmp( int i, int j ){
return job[ j ].first * job[ i ].second < job[ i ].first * job[ j ].second;
}

signed main(){
ios::sync_with_stdio( 0 );
int N; cin >> N;
for( int i = 0; i < N; ++i ){
cin >> job[ i ].first >> job[ i ].second;
ord[ i ] = i;
}
sort( ord, ord + N, cmp );
for( int i = 0; i < N; ++i ){
cout << ord[ i ] + 1 << "\n";
}
return 0;
}
```