会场安排问题

http://haoran-10.iteye.com/blog/1483316

 

java:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scannner = new Scanner(System.in);
        int m, n;
        m = scannner.nextInt();
        for (int i = 0; i < m; i++) {
            n = scannner.nextInt();
            List<Hui> list = new ArrayList<Hui>();
            for (int j = 0; j < n; j++) {
                Hui hui = new Hui();
                hui.start = scannner.nextInt();
                hui.end = scannner.nextInt();
                list.add(hui);
            }
            Collections.sort(list, new sort());
            int  num = 1;
            int end = list.get(0).end;
            for(int k=1;k<n;k++){
                if(list.get(k).start>end){
                    end = list.get(k).end;
                    num++;
                }
            }
            System.out.println(num);
        }
    }
}

class sort implements Comparator<Hui>{
    @Override
    public int compare(Hui o1, Hui o2) {
        return o1.end.compareTo(o2.end);
    }
}
class Hui {
    public Integer start;
    public Integer end;
}

c++

#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
struct activ
{
    int begin;
    int end;
};
bool cmp(activ a,activ b)
{
    return a.end<b.end;
}
int main()
{
    ifstream cin("input.txt");
    int n;
    cin>>n;
    while (n--)
    {
        int i,m;
        cin>>m;
        vector<activ> vec;
        for(i=0;i<m;i++)
        {
            activ a;
            cin>>a.begin>>a.end;
            vec.push_back(a);
        }
        sort(vec.begin(),vec.end(),cmp);   
        int count=vec.size();
        int k=0;
        for (i=1;i<vec.size();i++)
        {
            if(vec[i].begin <= vec[k].end)
                count--;
            else k=i;
        }
        cout<<count;
    }
    return 0;
}       

Advertisements
This entry was posted in algorithm and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s