· 9 years ago · Jan 21, 2017, 11:52 AM
1Problem: write a function to tell whether a series of workloads will exceed
2 the maximum workload or not
3
4Input: MaxWorkLoad: example 10
5 Timeslot and workload: example [(2, 6, 3), (3, 8, 2), ... ]
6 The (2, 6, 3) is begin time, end time, and workload
7 And it means from time 2 to time 6, the workload is 3
8 You can treat the 2, 6 as the UNIX epoch time.
9 The time may not be integers, so instead of 2, it can be 2.2
10 The input can be in any time order. For example: [(20, 60, 3), (3, 8, 2)]
11 The workload will "add up", so a 3 and 2 will add up to 5
12
13Output: a boolean indicating whether the series of workload can fit in without
14 exceeding MaxWorkLoad
15
16dict[beginTime] ||= 0; // if not defined, then set it to 0
17dict[beginTime] += workload;
18
19dict[endTime] ||= 0;
20dict[endTime] -= workload;
21
22Problem: write a function to tell whether a series of workloads will exceed
23 the maximum workload or not
24
25Input: MaxWorkLoad: example 10
26 Timeslot and workload: example [(2, 6, 3), (3, 8, 2), ... ]
27 The (2, 6, 3) is begin time, end time, and workload
28 And it means from time 2 to time 6, the workload is 3
29 You can treat the 2, 6 as the UNIX epoch time.
30 The time may not be integers, so instead of 2, it can be 2.2
31 The input can be in any time order. For example: [(20, 60, 3), (3, 8, 2)]
32 The workload will "add up", so a 3 and 2 will add up to 5
33
34Output: a boolean indicating whether the series of workload can fit in without
35 exceeding MaxWorkLoad
36
37drop schema if exists t1 cascade;
38create schema t1;
39set search_path='t1';
40create table segment
41(
42 start_dt bigint,
43 end_dt bigint,
44 load bigint
45);
46create index segment_idx_start_dt on segment(start_dt);
47create index segment_idx_end_dt on segment(end_dt);
48
49create or replace function segment_add(bigint,bigint,bigint) returns void as $$
50declare
51 xr1 record;
52 xr2 record;
53 xr3 record;
54 xs bigint;
55begin
56 raise info 'segment_add(%,%,%)', $1, $2, $3;
57 -- select all segments where the $1 is in (one or zero)
58 select into xr1 * from segment where $1 > start_dt and $1 < end_dt;
59 if xr1 is not null then
60 -- Split the segment on point $1
61 raise info 'add % % % ($1)', xr1.start_dt, $1, xr1.load;
62 raise info 'add % % % ($1)', $1, xr1.end_dt, xr1.load;
63 insert into segment values
64 ( xr1.start_dt, $1, xr1.load ),
65 ( $1, xr1.end_dt, xr1.load );
66
67 raise info 'del % %', xr1.start_dt, xr1.end_dt;
68 delete from segment where start_dt = xr1.start_dt and end_dt=xr1.end_dt;
69
70 end if;
71
72 -- select all segments where the $2 is in (one or zero)
73 select into xr2 * from segment where $2 > start_dt and $2 < end_dt;
74 if xr2 is not null then
75 -- split the segment on pont $2
76 raise info 'add % % % ($2)', xr2.start_dt, $2, xr2.load;
77 raise info 'add % % % ($2)', $2, xr2.end_dt, xr2.load;
78 insert into segment values
79 ( xr2.start_dt, $2, xr2.load ),
80 ( $2, xr2.end_dt, xr2.load );
81
82 raise info 'del % %', xr2.start_dt, xr2.end_dt;
83 delete from segment where start_dt = xr2.start_dt and end_dt=xr2.end_dt;
84
85 end if;
86
87 -- add segments that does not exist yet
88 xs = $1;
89 for xr3 in
90 select * from segment where start_dt between $1 and $2 order by start_dt
91 loop
92 if xs < xr3.start_dt then
93 -- there is no segment before the space
94 raise info 'add % % % (2)', xs, xr3.start_dt, 0;
95 insert into segment values (xs,xr3.start_dt,0);
96 end if;
97 xs = xr3.end_dt;
98 end loop;
99
100 if xs < $2 then
101 raise info 'add % % % (3)', xs, $2, 0;
102 insert into segment values (xs,$2,0);
103 end if;
104
105 -- now I must have all the fragment created.... I just need to update it
106 update
107 segment
108 set
109 load = load + $3
110 where
111 start_dt >= $1 and end_dt <= $2
112 ;
113
114end
115$$ language 'plpgsql';
116
117select segment_add(0,4000,6000);
118select segment_add(1000,10000,5000);
119select segment_add(12000,15000,5000);
120select segment_add(13000,14000,6000);
121-- the answer should have 0-1 1-4 4-10 12-13 13-14 14-15
122select * from segment order by start_dt;
123
124public static bool WorkLoadN(int[,] workload, int max)
125{
126 int rowCount = workload.GetLength(0);
127 int colCount = workload.GetLength(1);
128 int[] loadNet = new int[rowCount];
129 int start;
130 int end;
131 int load;
132 bool underMax = true;
133 for (int i = rowCount - 1; i >= 0; i--) // process in reverse order to show it does not need order
134 {
135 start = workload[i, 0];
136 end = workload[i, 1];
137 if (end > rowCount - 1)
138 end = rowCount - 1;
139 load = workload[i, 2];
140 for (int j = start; j <= end; j++)
141 loadNet[j] += load;
142 }
143 Debug.WriteLine("");
144 for (int i = 0; i < rowCount; i++)
145 {
146 Debug.WriteLine("loadNet[{0}] {1}", i, loadNet[i]);
147 if (loadNet[i] > max)
148 {
149 Debug.WriteLine("max exceeded loadNet[{0}] {1}", i, loadNet[i]);
150 underMax = false;
151 }
152 }
153 return underMax;
154}
155
156// this is just the test code to test
157public static void WorkLoadTestN()
158{
159 int rowCount = 20;
160 int max = 100;
161 int[,] workload = new int[rowCount, 3];
162 for (int i = 0; i < rowCount; i++)
163 {
164 workload[i, 0] = i;
165 workload[i, 1] = i + rand.Next(1, max / 6);
166 workload[i, 2] = rand.Next(max / 4);
167 Debug.WriteLine("intput start {0} end {1} load {2}", i, workload[i, 1], workload[i, 2]);
168 }
169 bool underMax = WorkLoadN(workload, max);
170}