earthSaver

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<pair<int,int>> record;
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        record.push_back(make_pair(a,b));
    }
    sort(record.begin(),record.end());
    int count = 2;
    //l和r表示选点区间
    int l = record[0].first;
    int r = record[0].second;
    for(int i=1;i<record.size();i++){
        if(record[i].first>=l&&record[i].first<=r){
            l = record[i].first;
            r = min(r,record[i].second);
        }else{
            count += 2;
            l = record[i].first;
            r = record[i].second;
        }
    }
    cout<<count<<endl;
    return 0;
}

发表于 2019-10-23 19:25:17 回复(3)

超越姐姐保佑我i

题意：选择一些点，保证每个区间至少包含这些点中的两个。

目标：让这些选点的数量尽可能的少。

主要思路：区间右端排序 + 贪心

百度搜《区间选点》，有一大堆写的很好的博客，看了就懂了。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n][2];
        for(int i = 0; i < n; i ++) {
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }
 
        Arrays.sort(arr, (e1, e2) -> e1[1] - e2[1]);
 
        LinkedList<Integer> list = new LinkedList<>();
        list.add(arr[0][1] - 1);
        list.add(arr[0][1]);
        for(int i = 1; i < n; i ++) {
            if(arr[i][0] > list.peekLast()) { // 相离
                list.add(arr[i][1] - 1);
                list.add(arr[i][1]);
            } else if(arr[i][0] > list.get(list.size() - 2)) {
                list.add(arr[i][1]);
            }
        }
        
        System.out.println(list.size());
    }
}

编辑于 2019-09-04 17:51:33 回复(3)

FlushHip

招商银行信用卡中心2019秋招IT笔试(AI、开发、测试开发方向)第三批

https://blog.csdn.net/FlushHip/article/details/84138227

发表于 2018-11-19 22:45:30 回复(0)

Learn2Learn

#贪心,按右端排序后，遍历区间，如果遍历到的区间代表数不够，每次优先取最右两个数
def slove(a):
    a.sort()
    set1=set()
    for l in a:
        s=l[-1]
        e=l[0]
        cn=0
        for i in range(s,e+1):
            if i in set1:
                cn+=1
            if cn==2:
                break
        if cn==0:
            set1.add(e-1)
            set1.add(e)
        if cn==1:
            set1.add(e)
    return len(set1)
        
        
if __name__=="__main__":
    n=int(input().strip())
    a=[]
    for i in range(n):
        l=list(map(int,input().strip().split()))
        a.append(l[::-1])
    if n==0:
        print(0)
    else:
        print(slove(a))

编辑于 2019-03-07 19:55:41 回复(0)

dragonlogin

// 右端排序 贪心
#include<bits/stdc++.h>
using namespace std;
struct P
{
	int s, e;
};
int main() {
	int n = 0;
	cin >> n;
	P *p = new P[n];
	for (int i=0; i<n; ++i) {
		cin >> i[p].s >> i[p].e;
	}
	sort(p, p+n, 
		[](P& a, P& b) {
		return a.e < b.e;
	} 		
	);
    int ans = 2;
    int l = 0[p].s;
    int r = 0[p].e;
    for (int i=1; i<n; ++i) {
        if (r >= i[p].s) {
            if (r - i[p].s + 1 < 2) {
                ++ans;
                r = i[p].e;
            } 
        } else {
                ans += 2;
                l = i[p].s;
                r = i[p].e;
       }
    }
    cout << ans << endl;
	
	delete p;
	return 0;
}

发表于 2019-10-22 17:51:56 回复(0)

C/C++

nbgao

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

struct P{
    int a, b;
    P(){}
    P(int a, int b):a(a),b(b){}
};

bool cmp(P p1, P p2){
    return p1.b < p2.b;
}

int main(){
    int n;
    cin>>n;
    P p[n];
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        p[i] = P(x,y);
    }
    sort(p,p+n,cmp);
    int cnt = 0, l=-1, r=-1;
    for(int i=0;i<n;i++){
        if(p[i].a > l){
            cnt++;
            l = r;
            r = p[i].b;
        }
        if(p[i].a > l){
            cnt++;
            l = p[i].b-1;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

发表于 2019-07-19 10:17:53 回复(0)

C/C++

ElonB

/*
贪心算法，参考课程安排
按右端排序，若挑选的数不在区间内，尽可能取右端
每次更新p1计数
*/
#include<bits/stdc++.h>
using namespace std;
#define N 10000
struct area {
    int a, b;
};

bool cmp(pair<int, int> x, pair<int, int> y)
{
    return x.second < y.second;
}


int main()
{
//    freopen("input.txt", "r", stdin);
    int n, i;
    cin >> n;
    vector<pair<int, int> > a(n);
    for(i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
    }
    sort(a.begin(), a.end(), cmp);
    int p1 = -1, p2 = -1, ans = 0;
    for(i = 0; i < n; i++) {
        if(a[i].first > p1) {
            ans++;
            p1 = p2;
            p2 = a[i].second;
        }
        if(a[i].first > p1) {
            ans++;
            p1 = a[i].second - 1;
        }
    }
    cout << ans << endl;
    return 0;
}

发表于 2019-07-11 21:48:44 回复(3)

.晚安

N, l = int(input()), []
a = [tuple(map(int, input().split())) for i in range(N)]
b = [a[i][1] for i in range(N)]
while b:
    m = min(b)
    i = b.index(m)
    if not l or a[i][0] > l[-1]: l += [m - 1, m]
    elif l[-2] < a[i][0] <= l[-1]: l.append(m)
    b.pop(i)
    a.pop(i)
print(len(l))

发表于 2020-07-15 14:35:53 回复(0)

hackjus20180919093142

    private static class Line{
        int left,right;
        public Line(int left,int right){
            this.left=left;
            this.right=right;
        }
    }
   
    public static void main (String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(bf.readLine());
        Line[]lines=new Line[n];
        for (int i = 0; i < n; i++) {
            String[]s=bf.readLine().split(" ");
            lines[i]=new Line(Integer.parseInt(s[0]),Integer.parseInt(s[1]));
        }
        int cnt=2;
        Arrays.sort(lines,0,n,new cmp());
        int l1=lines[0].right;
        int l2=lines[0].right-1;
        for (int i = 1; i < n ; i++) {
            if (l1<lines[i].left){
                cnt+=2;
                l1=lines[i].right;         
            }
            else if (l1==lines[i].left){
                cnt+=1;
                l1=lines[i].right;
            }else{
                continue;
            }
   
        }
   
   
        System.out.println(cnt);
   
    }
    private static class cmp implements Comparator<Line> {
        @Override
        public int compare(Line o,Line k) {
            int t=o.right-k.right;
            if (t==0){
                t=k.left-o.left ;
            }
            return t;
        }
    }

发表于 2020-05-07 22:43:22 回复(0)

Python

南瓜风

Python 为什么res用列表就会显示超时

n=int(input())
import sys
data=[]
for i in range(n):
    data.append(list(map(int,sys.stdin.readline().strip().split())))
#区间找点问题,按右端排序
data=sorted(data,key=lambda x:x[1])
res=set()
for i in data:
    count=0
    for k in range(i[0],i[1]+1):
        if k in res:
            count+=1
        if count==2:
            break
    if count==0:
        res.add(i[-1]-1)
        res.add(i[-1])
    if count==1:
        res.add(i[-1])
print(len(res))

发表于 2020-03-26 22:31:29 回复(0)

牛客508488410号

这种办法还可以做每个区间取不同点的情况，只需要把intervals类的constructor加一个对pointNumber的初始化操作
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            intervals[] intervals = new intervals[n];
            for (int i = 0;i < n;i++)
                intervals[i] = new intervals(scanner.nextInt(),scanner.nextInt());

            Arrays.sort(intervals);
            int max = intervals[n - 1].right;
            int[] axis = new int[max + 1];
            for (int i = 0;i < n;i++){
                int left = intervals[i].left;
                int right = intervals[i].right;
                int sum = sum(axis,left,right);
                int gap = intervals[i].pointNumber - sum;
                while (gap > 0){
                    if (axis[right] == 0) {
                        axis[right--] = 1;
                        gap--;
                    }
                    else right--;
                }
            }
            System.out.println(sum(axis,0,max));
        }
    }

    public static int sum(int[] axis,int left,int right){
        int sum = 0;
        for (int i = left;i <= right;i++)
            sum += axis[i];
        return sum;
    }

    public static class intervals implements Comparable<intervals>{
        public int left;
        public int right;
        public int pointNumber = 2;

        public intervals(int left,int right){
            this.left = left;
            this.right = right;
        }

        @Override
        public int compareTo(intervals other) {
            int temp = this.right - other.right;
            return temp != 0 ? temp : this.left - other.left;
        }
    }
}

发表于 2020-03-17 12:15:57 回复(0)

海拉鲁老实人

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
int main(){
    int n,beg,end,res=0,t;
    cin>>n;
    vector<pair<int,int>> itval;
    set<int> sel;
    for(int i=0;i<n;i++){
        cin>>beg>>end;
        itval.push_back(make_pair(end,beg));
    }
    sort(itval.begin(),itval.end());
    sel.insert(itval[0].first);
    sel.insert(itval[0].first-1);
    set<int>::iterator iter;
    for(int i=1;i<n;i++){
        iter=sel.lower_bound(itval[i].second);
        t=2;
        while(t>0&&iter!=sel.end()&&*iter>=itval[i].second&&*iter<=itval[i].first){
            t--;
            iter++;
        }  
        if(t==2){
            sel.insert(itval[i].first);
            sel.insert(itval[i].first-1);
        }else if(t==1){
            sel.insert(itval[i].first);
        }else 
            ;
    }
    cout<<sel.size()<<endl;
    return 0;
}

没有看出来这个和课程安排思路是一致的😂，按右端点排序，然后添加区间最右边两个点，新区间添加时检查区间内已经有几个点了，然后再决定是否再加点。

编辑于 2020-03-01 11:44:36 回复(0)

C/C++

Shopee内推小虾米

//#include "utils.cpp"
#include <bits/stdc++.h>
using namespace std;
//freopen("temp.in","r",stdin);
#include <bits/stdc++.h>
using namespace std;

/*
    贪婪法 区间按最右端 从小到大排序
    p1,p2表示前一区间选择的点(开始时是第一个区间最右边两点)
        判定现在的区间是否包含  包含则跳过
        不包含时  用新区间最右边两点替换
        只包含右边一点时，p1=p2，p2=新区间最右边点
*/
struct T{
    int a;
    int b;
    T(){}
    T(int a_,int b_):a(a_),b(b_){}
    //按区间最右端 从小到大排序
    bool operator<(const T &t){
        if(b==t.b) return a<t.b;
        return b<t.b;
    }
};

int main(){
	//freopen("temp.in","r",stdin);
    int N;
    cin>>N;
    int a,b;
    vector<T> A(N);
    for(int i=0;i<N;i++){
        cin>>a>>b;
        A[i]=T(a,b);
    }
    sort(A.begin(),A.end());
    
    bool token = false;//与前面区间的重合长度是否为1
    int ans = 2;
    int p1,p2;//选中的两个点
    p1 = A[0].b-1,p2 = A[0].b;
    for(int i=1;i<N;i++){
        //新区间与选中的点无交集 更新两点
        if(A[i].a>p2){
            ans+=2;
            p1=A[i].b-1;
            p2=A[i].b;
            continue;
        }
        //完全包含两点
        if(A[i].a<=p1 and A[i].b>=p2) continue;
        //仅包含右边点 因为区间是按右端升序的
        if(A[i].a>p1 and A[i].a<=p2){
            ans+=1;
            p1 = p2;
            p2 = A[i].b;
        };
    }
    cout<<ans<<endl;
    return 0;
}

发表于 2020-02-16 17:48:07 回复(0)

1辰

import java.util.*;

public class Main {
    public static class seg {
        public int a;
        public int b;
        public seg(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }

    public static class segSort implements Comparator<seg> {
        public int compare(seg i1, seg i2) {
            return i1.b != i2.b ? i1.b - i2.b : i2.a - i1.a;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        seg[] s = new seg[n];
        for(int i = 0; i < n; i ++) {
            int a = in.nextInt();
            int b = in.nextInt();
            s[i] = new seg(a, b);
        }
        Arrays.sort(s, new segSort());
        int p1 = s[0].b - 1;
        int p2 = s[0].b;

        int count = 2;
        for(int i = 1; i < n; i ++) {
            if(s[i].a <= p1 && s[i].b >= p2)
                continue;
            else if(s[i].a <= p2) {
                count += 1;
                p1 = s[i].b - 1;
                p2 = s[i].b;
            }
            else if(s[i].a > p2) {
                count += 2;
                p1 = s[i].b - 1;
                p2 = s[i].b;
            }
        }

        System.out.println(count);
    }
}

发表于 2019-10-18 18:07:03 回复(0)

YLQ127

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

int main(){
    int n;
    cin >> n;
    map<int,int> m;
    int a,b;
    for(int i=0;i<n;i++){
        cin >> a >> b;
        m.insert({b,a}); //按右区间排序
    }
    map<int,int>::iterator p;
    p=m.begin();
    int a1 = p->first -1; //把第一个区间先取两个值，右区间-1 和 右区间
    int b1 = p->first;
    //cout << a1 << " " << b1 << endl;
    int num=2; 
    for(int i=1;i<n;i++){
        p++;
        if(a1 >= p->second && b1 <= p->first)    continue; //包含该两个点，无需再取值
        if(b1 < p->second){ //区间该两点都不包含
            num = num+2;
            a1 = p->first -1;
            b1 = p->first;
            //cout << "2222" << endl;
            //cout << "p:" << p->second << " "<< p->first << endl;
            //cout << a1 << " " << b1 << endl;
        }
        if(a1 < p->second && b1 <= p->first){ //区间包含一个点 肯定是前一个点 a1 。。。所以重新取 b1 即可
            cout << "p:" << p->second << " " << p->first << endl;
            num++;
            a1 = b1;
            b1 = p->first;
            //cout << "1111" << endl;
            //cout << a1 << " " << b1 << endl;
        }
    }
    cout << num << endl;
    return 0;
}

发表于 2019-09-19 16:12:36 回复(0)

tempest111

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] nums = new int[n][2];
        for (int i = 0; i < n; i++) {
            nums[i][0] = sc.nextInt();
            nums[i][1] = sc.nextInt();
        }
        Arrays.sort(nums, Comparator.comparingInt(o -> o[1]));
        int cnt = 1, end = nums[0][1];
        for (int i = 1; i < n; i++) {
            if (nums[i][0] <= end) {
                continue;
            }
            cnt++;
            end = nums[i][1];
        }
        System.out.println(cnt * 2);
    }
}

发表于 2019-09-19 15:27:18 回复(0)

Java

JLU小浪

import java.util.Arrays;
import java.util.Scanner;
//52
/*右端点排序,按条件判断(倾向于选最右边的)*/
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[][] a = new int[n][2];
		for (int i = 0; i < n; i++) {
			a[i][0] = sc.nextInt();
			a[i][1] = sc.nextInt();
		}
		Arrays.sort(a, (a1, a2) -> a1[1] - a2[1]); // 右端点排序
		int res = 2;// 至少需要两个
		int temp = a[0][1];
		for (int i = 1; i < n; i++) {
			if (a[i][0] > temp) {
				res += 2;
				temp = a[i][1];
			} else if (a[i][0] == temp) {
				res += 1;
				temp = a[i][1];
			}
		}
		System.out.println(res);

	}
}

编辑于 2019-09-15 18:18:06 回复(1)

Kevin亓

import java.util.*;
public class Main {
    public static void main(String[] args) {
    	// 1、输入
    	Scanner sc = new Scanner(System.in);
    	int N = sc.nextInt();
    	int[][] arr = new int[N][2];
    	for(int i = 0; i < N; i++) {
    		arr[i][0] = sc.nextInt();
    		arr[i][1] = sc.nextInt();
    	}
    	// 2、排序（按照区间右端排序）
    	Arrays.sort(arr, new Comparator<int[]>() {
    		public int compare(int[] a, int[] b) {
    			return a[1] - b[1];
    		}
    	});
    	
    	if(N == 1) {
    		System.out.println(2);
    		return;
    	}
    	if(N < 1) {
    		System.out.println(0);
    		return;
    	}
    	
    	// 3、贪心
    	LinkedList<Integer> list = new LinkedList<>();
    	list.add(arr[0][1]-1);
    	list.add(arr[0][1]);
    	
    	for(int i = 1; i < N; i++) {
    		if(arr[i][0] > list.getLast()) {
    			list.add(arr[i][1]-1);
    			list.add(arr[i][1]);
    		}else if(arr[i][0] > list.get(list.size()-2)) {
                list.add(arr[i][1]);
            }
    	}
    	System.out.println(list.size());
    }
}

编辑于 2019-09-15 16:02:25 回复(2)

林林七__

def min_num(nums):
    nums.sort(key=lambda x:x[1])
    count = 0
    pre_sec = [-float('inf'), -float('inf')]
    for left, right in nums:
        if left > pre_sec[1]:
            count += 2
            pre_sec = [right-1, right]

        elif pre_sec[0] < left and left <= pre_sec[1]:
            count += 1
            pre_sec = [pre_sec[1], right]

    return count


n = int(input())
nums = []
for i in range(n):
    nums.append([int(x) for x in input().split()])
print(min_num(nums))

发表于 2019-08-28 15:25:54 回复(0)

Python

贾志统

def func(n, sections):
    sections.sort()
    bi = sections[0][0]
    select_nums = [bi - 1, bi]
    for section in sections:
        ai = section[1]
        bi = section[0]
        if ai <= select_nums[-2]:
            continue
        elif ai <= select_nums[-1]:
            select_nums.append(bi)
        else:
            select_nums.append(bi)
            select_nums.append(bi - 1)
    print(len(select_nums))


n = int(input())
sections = []
for i in range(n):
    ai, bi = map(int, input().split())
    per_section = (bi, ai)
    sections.append(per_section)
func(n, sections)

发表于 2019-08-28 15:12:32 回复(0)

挑选代表

输入描述:

输出描述:

输入

输出

招商银行信用卡中心2019秋招IT笔试(AI、开发、测试开发方向)第三批

问题信息

热门推荐

通过挑战的用户

相关试题