c - Data Structure: Request Counting Task -

c - Data Structure: Request Counting Task -

i looking @ programming task , found next question. problem statement: list of professionals start_time , end_time given. list of end_tasks tasks given. find number of tasks each professional can within timeframe.

inputs: requests: [4,2,5,3,1], start_time: [2,5], end_time: [5,6].

output: 4 1

explanation: since professional_1 has time_frame 2 5, can perform 4 tasks(4,2,5,3) , professional_2 has time frame 5 6, , can 1 task(i.e., 5)

program code:

#include <stdio.h> void count_requests(int *requests, int requests_length, int *pro_start, int pro_start_length, int *pro_end, int pro_end_length) { int i,j,req,start,end,task; for(i=0;i<pro_start_length;i++){ start=*(pro_start+i); end=*(pro_end+i); task=0; for(j=0;j<requests_length;j++){ req=*(requests+j); if(req>=start && req<=end){ task=task+1; } } printf("%d\n",task); } }

the nested for-loop here takes more 30 seconds run when inputs of order 50000. missing here?

right you're iterating through entire list of inputs each worker. instead, can sort list of inputs , perform 2 binary searches each worker determine indices of tasks within bounds

sortedinputs = sort(inputs) for(i=0;i<pro_start_length;i++){ startindex = binarysearch(sortedinputs, *(pro_start+i)); endindex = binarysearch(sortedinputs, *(pro_end+i)); printf("%d\n",endindex - startindex) }

you've got initial o(n*log(n)) cost front end when sort inputs, cost of each task count o(log(n))

if instead you've got fixed set of workers , stream of requests (so it's not practical sort requests) create segment tree of workers, , each request retrieve set of workers can fulfill request. has same complexity - o(n*log(n)) create segment tree, , o(log(n)) query tree each request.

c algorithm data-structures