首页 > 试题广场 >

查询满足区间的记录

[编程题]查询满足区间的记录
  • 热度指数:4680 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
有一批订单记录,数据有订单号,入店时间,离店时间;
输入一个时间值A,需要在这批记录中找到符合入离店时间范围(A大于等于入店时间,并且A小于等于离店时间)内的所有记录。 单次查询时间复杂度控制在O(logN)
※注意:订单号升序输出 

输入描述:
记录数:10
时间值A:20180602
订单号 入店时间 离店时间
1001 20180103 20180105
1002 20180202 20180203
1003 20180304 20180306
1004 20180401 20180408
1005 20180501 20180504
1006 20180601 20180604
1007 20180705 20180706
1008 20180801 20180804
1009 20180903 20180903
1010 20181003 20181003
以上输入都为整型


输出描述:
1006
示例1

输入

10
20180602
1001 20180103 20180105
1002 20180202 20180203
1003 20180304 20180306
1004 20180401 20180408
1005 20180501 20180504
1006 20180601 20180604
1007 20180705 20180706
1008 20180801 20180804
1009 20180903 20180903
1010 20181003 20181003

输出

1006
示例2

输入

5
20170103
1013 20180103 20180105
1022 20180102 20180103
1103 20180104 20180106
1034 20180101 20180102
1105 20180201 20180204

输出

null

说明

查不到时输出null字符串(小写)
示例3

输入

4
20180103
1013 20180103 20180105
1022 20180102 20180103
1026 20180103 20180103
1007 20180101 20180109

输出

1007
1013
1022
1026

没有什么特别好的办法啊,只能对入住时间排序,然后采用二分查找,再验证离开时间是否满足要求,如果有更好的解法,麻烦@我一下,谢谢。

#include <bits/stdc++.h>

using namespace std;

struct Dindan
{
    long num, in, out;
};

bool cmp(Dindan a, Dindan b)
{
    return a.in < b.in;
}

int BinarySearch(vector<Dindan> v, int data)
{
    int left = 0, right = v.size();    
    while (left < right)
    {
        int mid = (left + right) / 2;
        if (v[mid].in <= data)
            left = mid + 1;
        else
            right = mid;
    }
    return left;
}

int main()
{
    int n, data;
    cin >> n >> data;
    vector<Dindan> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i].num >> v[i].in >> v[i].out;
    sort(v.begin(), v.end(), cmp);
    vector<int> res;
    int end = BinarySearch(v, data);
    for (int i = 0; i < end; i++)
        if (v[i].out >= data)
            res.push_back(v[i].num);
    if (res.empty())
    {
        cout << "null" << endl;
    }
    else
    {
        sort(re***egin(), res.end());
        for (int i : res)
            cout << i << endl;
    }
    system("pause");
    return 0;
}
发表于 2019-05-17 16:36:15 回复(3)
#include <stdio.h>
#include <stdlib.h>

typedef struct {
  int id;       /** 订单ID  */
  int in_time;  /** 到店时间 */
  int out_time; /** 离店时间 */
} Order;

// =============== function prorotype ===============
// 按订单的到店时间升序排序(由小至大)
int compare_1(const void* a, const void* b);

// 按订单的离店时间升序排序(由小至大)
int compare_2(const void* a, const void* b);

int compare_3(const void* a, const void* b);

// 打印所有的订单信息
void printOrders(Order orders[], const int size);
// =============== function prorotype ===============

// global variable
int (*cmp)(const void*, const void*) = compare_1;

int main(void) {
  int i, n, a, sz;
  scanf("%d %d", &n, &a);
  
  Order orders[n];
  for (i = 0; i < n; ++i) {
    scanf("%d %d %d", &orders[i].id, &orders[i].in_time, &orders[i].out_time);
//     printf("%d %d %d\n", orders[i].id, orders[i].in_time, orders[i].out_time);
  }
  
  qsort(orders, n, sizeof(Order), cmp);
  
  // 二分查找法:
  // Template: [low, high)
  int low = 0, high = n, middle;
  while (low < high) {
    middle = low + ((high - low) >> 1);
    if (orders[middle].in_time > a) // 寻找最左边 > a ,变相就是寻找最右边 <= a
      high = middle;    // 收缩右边界
    else
      low = middle + 1; // 收缩左边界 
  }
  
  sz = low;
  Order tmp[sz]; // 保存了到店时间早于或等于A的所有订单
  memcpy(tmp, orders, sz * sizeof(Order));
  
  cmp = compare_2;
  qsort(tmp, sz, sizeof(Order), cmp);
  
  low = 0, high = sz;
  while (low < high) {
    middle = low + ((high - low) >> 1);
    if (tmp[middle].out_time >= a) // be careful!!
      high = middle;    // 收缩右边界
    else
      low = middle + 1; // 收缩左边界 
  }
  
  sz -= low;
  if (!sz)
    return puts("null"), 0;
  
  int ret[sz];
  for (i = 0; i < sz; ++i)
    ret[i] = tmp[low + i].id;
  
  cmp = compare_3;
  qsort(ret, sz, sizeof(int), cmp);
  
  for (i = 0; i < sz; ++i)
    printf("%d\n", *(ret + i));
  
  return 0;
}

int compare_1(const void* a, const void* b) { 
  return ((Order*) a)->in_time - ((Order*) b)->in_time;
}

int compare_2(const void* a, const void* b) {
  return ((Order*) a)->out_time - ((Order*) b)->out_time;
}

int compare_3(const void* a, const void* b) {
  return *((int*) a) - *((int*) b);
}


void printOrders(Order orders[], const int size) {
  int i;
  printf("%-15s%-15s%-15s\n", "订单号", "到店时间", "离店时间");
  for (i = 0; i < size; ++i)
    printf("%-15d%-15d%-15d\n", orders[i].id, orders[i].in_time, orders[i].out_time);
  putchar('\n');
}

发表于 2021-07-05 11:19:49 回复(0)
#include <bits/stdc++.h>
using namespace std;

struct P{
    int id, s, e;
};

int main(){
    int n, t, cnt=0;
    cin>>n>>t;
    P p[n];
    set<int> v;
    for(int i=0;i<n;i++){
        cin>>p[i].id>>p[i].s>>p[i].e;
        if(p[i].s<=t && p[i].e>=t)
            v.insert(p[i].id);
    }
    if(v.size()==0)
        cout<<"null"<<endl;
    else{
    for(auto s: v)
        cout<<s<<endl;
    }    

    return 0;
}

发表于 2019-10-13 11:18:39 回复(0)
importjava.util.*;
 
public clas***ain{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        intx = in.nextInt();//记录数;
        intA = in.nextInt();//时间值;
        int[][] a = newint[x][3];//记录信息;
        for(inti = 0; i <x ; i++) {
            for(intj = 0; j <3; j++) {
                a[i][j] = in.nextInt();
            }
        }
         
        TreeSet<Integer> set = new TreeSet<Integer>();
 
        for(inti = 0; i < x ; i++) {
            for(intj = 0; j < 3; j++) {
                if(a[i][1] <= A && A <= a[i][2]){
                    set.add(a[i][0]);
                }
            }
        }
        if(set.size()==0)
            System.out.println("null");
        Iterator it = set.iterator();
        intk = 0;
        while(it.hasNext())//判断是否有下一个
        {
            k = (int) it.next();
            System.out.println(k);
        }
    }
}

发表于 2019-05-14 22:16:19 回复(0)
#include "bits/stdc++.h"
using namespace std;
typedef struct Dingdan
{
    string id;
    string startDate;
    string endDate;
} DD;
int main()
{
    int n;
    string date;
    while(cin>>n>>date)
    {
       cin.ignore();
        vector<DD> vec(n);
        string str;
        vector<string> ans;
        for(int i=0;i<n;i++)
        {
            getline(cin,str);
            stringstream ss(str);
            ss>>vec[i].id>>vec[i].startDate>>vec[i].endDate;
        }
        for(int i=0;i<n;i++)
        {
            if(vec[i].startDate<=date&&vec[i].endDate>=date)
                ans.push_back(vec[i].id);
        }
        sort(ans.begin(),ans.end());
        if(ans.empty())
            cout<<"null"<<endl;
        else
            for(auto i:ans)
                cout<<i<<endl;
    }
}

编辑于 2019-05-14 10:53:47 回复(0)
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a;
    cin>>a;
    vector<int>num(n),r(n),c(n),res;
    for(int i=0;i<n;i++)
    {
        cin>>num[i]>>r[i]>>c[i];
        if(a>=r[i]&&a<=c[i])
            res.push_back(num[i]);
    }
    if(res.size()==0)
        cout<<"null"<<endl;
    else
    {
        sort(res.begin(),res.end());
        for(int i=0;i<res.size();i++)
            cout<<res[i]<<endl;
    }
    return 0;
}

发表于 2019-08-17 22:17:49 回复(2)
import java.util.*;

public clas***ain {

    static clas***ill{
        int id;
        int inTime;
        int outTime;

        public bill(int id, int inTime, int outTime) {
            this.id = id;
            this.inTime = inTime;
            this.outTime = outTime;
        }

    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int A = in.nextInt();

        int[] ids = new int[n];
        int[] inTimes = new int[n];
        int[] outTimes = new int[n];

        bill[] bills = new bill[n];

        for (int i = 0; i < n; i++) {
            bills[i] = new bill(0,0,0);
            bills[i].id = in.nextInt();
            bills[i].inTime = in.nextInt();
            bills[i].outTime = in.nextInt();
        }
        Arrays.sort(bills, (o1, o2) -> o1.inTime - o2.inTime);

        for (int i = 0; i < n; i++) {
            ids[i] = bills[i].id;
            inTimes[i] = bills[i].inTime;
            outTimes[i] = bills[i].outTime;
        }

        int re***S(A, inTimes);
        boolean isNull = true;
        List<Integer> out = new ArrayList<>();
        for (int i = 0; i <= res; i++) {
            if (inTimes[res] <= A && outTimes[i] >= A) {
                //System.out.println(ids[i]);
                out.add(ids[i]);
                isNull = false;
            }
        }
        out.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        if (isNull) {
            System.out.println("null");
        } else {
            for (int i = 0; i < out.size(); i++) {
                System.out.println(out.get(i));
            }
        }

    }

    static int BS(int target, int[] nums) {
        int l = 0;
        int r = nums.length - 1;

        while (l + 1 < r) {
            int mid = l + ((r - l) >> 1);

            if (num***id] > target) {
                r = mid;
            } else if (num***id] <= target) {
                l = mid;
            }
        }

        if (nums[r] == target) return r;

        return l;
    }
}
编辑于 2019-05-20 19:01:59 回复(1)
GO实现。直接比较(入住时间与离店时间的差值)与(时间值A与离店时间的差值)。如果后者小于等于前者,且后者大于等于0,即满足要求。将序号存入数组,最后对数组进行排序。
package main
 
import (
    "fmt"
    "sort"
)
func main(){
    var n, time int
    fmt.Scanln(&n)
    fmt.Scanln(&time)
    var ans []int
    for i := 0; i < n; i++ {
        var seq, startTime, endTime int
        fmt.Scanln(&seq, &startTime, &endTime)
        if endTime - startTime >= endTime - time&& (endTime - time) >= 0 {
            ans = append(ans, seq)
        }
    }
    if len(ans) == 0 {
        fmt.Println("null")
    } else {
        sort.Ints(ans)
        for _, v := range ans {
            fmt.Println(v)
        }
    }
     
}
欢迎指正
发表于 2019-05-19 17:19:56 回复(1)
/*
思路:把入店和离店时间转成int,然后与给定的时间进行比较,符合条件的存入集合
※注意:订单号升序输出,sort方法
*/

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int timeA = Integer.parseInt(br.readLine());
        //int count = 0;
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0;i < n;i++){
            String[] str = br.readLine().split(" ");
            int orderid = Integer.parseInt(str[0]);
            int intime = Integer.parseInt(str[1]);
            int outtime = Integer.parseInt(str[2]);
            if(timeA >= intime && timeA <= outtime){
                list.add(orderid);
            }
        }
        if(list.isEmpty())
            System.out.println("null");
        else{
            Collections.sort(list);
            for(Object obj:list)
                System.out.println(obj);
        }
    }
}

发表于 2020-05-22 14:00:38 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    int time;
    cin>>n>>time;
    vector<int> ans;
    for(int i=0;i<n;i++){
        int id,t1,t2;
        cin>>id>>t1>>t2;
        if(t1<=time&&t2>=time)
            ans.push_back(id);
    }
    if(ans.empty()){
        cout<<"null";
        return 0;
    }
    sort(ans.begin(),ans.end());
    for(int i:ans)
        cout<<i<<endl;
    return 0;
}

编辑于 2019-10-20 15:41:13 回复(0)

我的方法比较死板,但还好有效的,直接在输入的时候进行插入排序(根据ID),最后遍历输出。

package cn.bubbletg.test;

import java.util.Scanner;

public class test {


    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        //输入
        int N = in.nextInt();
        int date = in.nextInt();
        dingdan[] dd = new dingdan[N];
        for (int i = 0; i < N; i++) {
            dd[i] = new dingdan();
        }
        dd[0].id = in.nextInt();
        dd[0].date_q = in.nextInt();
        dd[0].date_h = in.nextInt();
        //直接使用插入排序
        for (int i = 1; i < N; i++) {
            dd[i].id = in.nextInt();
            dd[i].date_q = in.nextInt();
            dd[i].date_h = in.nextInt();


            //无序部分第一个值,即待插入值
            int value = dd[i].id;
            int valueq = dd[i].date_q;
            int valueh = dd[i].date_h;
            //有序部分最后一个值
            int yw = i - 1;
            //插入位置结束条件
            while (yw >= 0 && dd[yw].id > value) {

                //待插入值先前移动,有序部分向后移动
                dd[yw + 1].id = dd[yw].id;
                dd[yw + 1].date_q = dd[yw].date_q;
                dd[yw + 1].date_h = dd[yw].date_h;
                //让待插入值与有序部分倒数第(yw+) 比较
                yw--;
            }
            //待插入值插入,因为退出循环,说明位置找到(yw+1)
            dd[yw + 1].id = value;
            dd[yw + 1].date_q = valueq;
            dd[yw + 1].date_h = valueh;

        }


        boolean t = false;
        //按条件输出
        for (int i = 0; i < N; i++) {

            if (dd[i].date_q <= date && dd[i].date_h >= date) {
                System.out.println(dd[i].id);
                t = true;
            }
        }
        if (!t) {
            System.out.println("null");
        }


    }


}

class dingdan {
    //订单号
    public Integer id;
    public Integer date_q;
    public Integer date_h;
}







发表于 2019-09-22 09:50:18 回复(1)
分治算法,按照第二列时间排序后,分治查找并判断
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int target = sc.nextInt();
        int[][] nums = new int[n][3];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < 3; j++){
                nums[i][j] = sc.nextInt();
            }
        }
        Arrays.sort(nums, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        List<Integer> res = new ArrayList<>();
        getRes(res, nums, target, 0, nums.length - 1);
        if(res.isEmpty()){
            System.out.println("null");
            return ;
        }
        Collections.sort(res);
        for(int temp : res){
            System.out.println(temp);
        }
    }

    private static void getRes(List<Integer> res, int[][] nums, int target, int l, int h) {
        if(l > h) return ;
        int mid = l + (h - l) / 2;
        if(nums[mid][1] <= target && nums[mid][2] >= target){
            res.add(nums[mid][0]);
        }
        getRes(res, nums, target, l, mid - 1);
        getRes(res, nums, target , mid + 1, h);
    }
}


发表于 2021-04-01 15:19:46 回复(0)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);
        int log=sc.nextInt();
        int count =sc.nextInt();
        ArrayList<Integer> list =new ArrayList<>();
        for(int i=0;i<log;i++) {
            int a=sc.nextInt();
            int b=sc.nextInt();
            int c=sc.nextInt();
            if(b<=count&&c>=count) {
                list.add(a);
            }
        }
        if(list.isEmpty()) {
            System.out.println("null");
        }else {
            Collections.sort(list);
            for (Integer integer : list) {
                System.out.println(integer);
            }
        }
    }
}




我觉着我的代码还是比较简单的吧
发表于 2019-09-04 08:39:33 回复(3)

直接对输入判断,将合适的id放进一个数组里排序后把0过滤掉再输出

import java.util.Arrays;
import java.util.Scanner;
public class Test {
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int A = scan.nextInt();
        dingdan[] dd = new dingdan[N];
        for(int i = 0; i < N; i++) {
            dd[i] = new dingdan();
        }

        for(int i = 0; i < N ; i++) {
            dd[i].id = scan.nextInt();
            dd[i].inTime = scan.nextInt();
            dd[i].outTime = scan.nextInt();        
        }
        boolean ans = false;
        int []arr = new int[N];
        for(int i = 0; i < N ; i++) {
            if(A = dd[i].inTime) {
                arr[i] = dd[i].id;
                ans = true;
            }
        }
        Arrays.sort(arr);
        if(ans==false) {
            System.out.println("null");
        }else {
            for(int i = 0; i < N ; i++) {
                if(arr[i]==0) {
                    System.out.print("");
                }else {

                    System.out.println(arr[i]);
                }
            }    
        }    
    }    
}
class dingdan {

    int id;
    int inTime;
    int outTime;

}
编辑于 2021-05-08 11:03:38 回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n =Integer.valueOf(br.readLine());
        int[] nums = new int[n];
        int[] r = new int[n];
        int[] c= new int[n];
        List<Integer> res = new ArrayList<>();
        int time = Integer.valueOf(br.readLine());
        for (int i = 0; i < n; i++) {
            String[] s = br.readLine().trim().split(" ");
            nums[i]=Integer.valueOf(s[0]);
            r[i]=Integer.valueOf(s[1]);
            c[i]=Integer.valueOf(s[2]);
            if(time>=r[i]&&time<=c[i]){
                res.add(nums[i]);
            }
        }
        int[] ans = res.stream().mapToInt(Integer::intValue).toArray();

        if (res.size()==0){
            System.out.println("null");
        }else{
            Arrays.sort(ans);
            for (int i = 0; i < res.size(); i++) {
                System.out.println(ans[i]);
            }
        }

    }
}

集合和数组的转换
发表于 2021-04-26 20:10:10 回复(0)
很久没做过题偶然看到觉得挺有趣,就来试试,在学java,所以C++忘了大部分函数,写出来的代码有点低级。
题目理解:针对O(logn)要求:要么平台没有判断各位大佬的算法是否符合该要求,要么如果能过所有用例的算法都符合(开始卡用例bug)。
思路:二分法,然后只要找到一个包含要求时间的区间段,那么从这个区间段的左右区间段再找下去就行。
上代码:
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int number;
    int time;
    int res[101];
    int j = 0;
    int temp = 1;
    int flag = 0;
    scanf("%d", &number);
    scanf("%d", &time);
    int a[1024][3];
    int t[3];
    for(int i = 0; i < number; i++){
        scanf("%d %d %d", &a[i][0], &a[i][1], &a[i][2]);
    }
    for(int i = 0; i < number; i++){
        for(int k = i + 1; k < number; k++){
            if(a[i][1] > a[k][1]){
                t[0] = a[i][0];
                t[1] = a[i][1];
                t[2] = a[i][2];
                a[i][0] = a[k][0];
                a[i][1] = a[k][1];
                a[i][2] = a[k][2];
                a[k][0] = t[0];
                a[k][1] = t[1];
                a[k][2] = t[2];
            }
        }
    }
    int left = 0;
    int right = number - 1;
    int middle = 0;
    res[j] = -1;
    int n = number;
    while(n--){
        middle = (left + right) / 2;
        if(time >= a[middle][1] && time <= a[middle][2]){
            res[j] = a[middle][0];
            j++;
            while(1){
                flag = 0;
                if(middle - temp >= 0 && time >= a[middle - temp][1] && time <= a[middle - temp][2]){
                    res[j++] = a[middle - temp][0];
                    flag = 1;
                }
                res[j] = a[middle - temp][0];
                if(middle + temp <= number -1 && time >= a[middle + temp][1] && time <= a[middle + temp][2]){
                    res[j++] = a[middle + temp][0];
                    flag = 1;
                }
                temp++;
                if(!flag){
                    break;
                }
            }
            break;
        }
        if(time > a[middle][2]){
            left = middle;
        }
        if(time < a[middle][1]){
            right = middle;
        }
    }
    sort(res, res + j);
    
    if(res[j] != -1){
        for(int i = 0; i < j; i++){
            printf("%d\n", res[i]);
        }
    }else
    {
        printf("null");
    }
    return 0;
}
用例全过,但是不清楚是方法正确还是偶然过了所有用例。
过了才看到有个C++大佬的解法简单有效,膜拜。

发表于 2021-04-15 01:05:52 回复(0)
#!/bin/bash
read num
read target
sig=0
A=()
while [ $num -gt 0 ]
do
    read index minimum miximum
    if [ "$target" -ge "$minimum" ] && [ "$target" -le "$miximum" ]
    then
        sig=1
        A[${#A[@]}]=$index
    fi
    num=$(($num-1))
done
if [ $sig -eq 0 ]
then
    echo "null"
else
   echo ${A[@]} | tr " " "\n" | sort -n
fi

发表于 2021-04-14 14:16:50 回复(0)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int A = sc.nextInt();
        Set<Integer> result = new TreeSet<>();
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for(int i=0;i<n;i++){
            int key = sc.nextInt();
            int startTime = sc.nextInt();
            int endTime = sc.nextInt();
            Set<Integer> set = new TreeSet<>();
            for(int j=startTime;j<=endTime;j++){
             set.add(j);
            }
            if(set.contains(A)){
                result.add(key);
            }
        }
        if(!result.isEmpty()){
            for(Integer number:result){
                System.out.println(number);
            }
        }else{
            System.out.println("null");
        }

    }
}
充分利用Java集合,做完才发现和大家思路都不一样,感觉好像钻了空子
发表于 2020-12-17 17:52:08 回复(0)
哪位大佬帮我看看这是为啥??
发表于 2020-09-07 17:46:08 回复(0)
N=int(input())
t=int(input())
B=[]
for i in range(N):
    a,b,c = map(int,input().split())
    if b<=t<=c:
        B.append(a)
if len(B)==0:
    print('null')
else:
    B.sort()
for i in B:
    print(i)
发表于 2020-08-15 18:03:44 回复(0)