Code Festival : B - 枕決め

問題:

http://code-festival-2014-morning-middle.contest.atcoder.jp/tasks/code_festival_morning_easy_d
m人の人がいる。それぞれの人は好みの枕の高さの範囲[xi,yi]が与えられる。
n個の枕がある。それぞれの枕の高さはh[i]で、これも与えられる。
枕は一人一つ使うものとして、最大で何人の人が枕を使うことが出来るか、人数を求めよ。

解法:

貪欲法で解ける。
まずは点と区間でソートする。
priority_queueを用意する(突っ込むものは区間で、ソート基準は右側の座標の小さい順)

点x[i]について、
1.その点を含むような区間をすべてpriority_queueに入れる。
2.priority_queueから区間を取り出し、もしそれがx[i]を含むものであったらx[i]はその区間とマッチング。そうでないならばpriority_queueから点を取り出し続ける。
3.マッチングの個数を出力

KODER COMBAT : Divide It

Problem

https://www.hackerrank.com/contests/koder-kombat-mar/challenges/divide-it

Solution

When we used i segments and got t-divided paper and add a new segment to it , we can get k new intersections(k=0,1,...,i-1) and t+i+1-divided paper.
Let (t,i) is a state of t-divided paper using i segments.
Then, (t,i) -> (t+1,i+1) , (t+2,i+1) , ... (t+i-1,i+1).

Code

int main() {

    int t;cin>>t;

    while(t--){

        int m;cin>>m;

        for(int i=0;i<m;++i){

            if(1+i*(i+1)/2>=m){

                cout<<i<<endl;

                break;

            }

        }

    }

    return 0;

}