Форум программистов, компьютерный форум, киберфорум
Loafer
Войти
Регистрация
Восстановить пароль
Оценить эту запись

Intervals problem

Запись от Loafer размещена 25.03.2020 в 16:42

Поиск общих интервалов между массивами интервалов.

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
using System;
using System.Collections.Generic;
 
namespace intervals
{
    public class Program
    {
        public static List<int> CommonManyIntervals(List<List<int>> vectors)
        {
            List<int> result = CommonTwoIntervals(vectors[0], vectors[1]);
            for (int i = 2; i < vectors.Count; ++i)
            {
                result = CommonTwoIntervals(result, vectors[i]);
            }
            return result;
        }
 
        public static List<int> CommonTwoIntervals(List<int> a, List<int> b)
        {
            List<int> result = new List<int>();
            
            int aPtr = 0;
            int bPtr = 0;
 
            while (aPtr < a.Count && bPtr < b.Count)
            {
                if (a[aPtr] < b[bPtr])
                {
                    int next = a[aPtr + 1];
                    if (next < b[bPtr])
                    {
                        aPtr += 2;
                        continue;
                    }
                }
                else
                {
                    int next = b[bPtr + 1];
                    if (next < a[aPtr])
                    {
                        bPtr += 2;
                        continue;
                    }
                }
                
                int begin = Math.Max(a[aPtr], b[bPtr]);
                int end = Math.Min(a[aPtr + 1], b[bPtr + 1]);
 
                result.Add(begin);
                result.Add(end);
 
                if (a[aPtr + 1] < b[bPtr + 1])
                {
                    aPtr += 2;
                }
                else
                {
                    bPtr += 2;
                }
            }
            
            return result;
        }
 
        public static void Main()
        {
            Console.Write("Enter number of arrays: ");
            int arraysNumber = Convert.ToInt32(Console.ReadLine());
 
            if (arraysNumber < 2)
            {
                Console.WriteLine("Number of arrays must be greater than one");
                return;
            }
            
            Random random = new Random();
            List<List<int>> vectors = new List<List<int>>();
            for (int i = 0; i < arraysNumber; ++i)
            {
                int length;
                do
                {
                    length = random.Next(MAX_LENGTH);
                }
                while (length % 2 != 0);
 
                List<int> vector = new List<int>();
                for (int j = 0; j < length; ++j)
                {
                    vector.Add(random.Next(MAX_VALUE));
                }
                vector.Sort();
                vectors.Add(vector);
            }
 
            foreach(List<int> vector in vectors)
            {
                Console.Write("# ");
                foreach(int number in vector)
                {
                    Console.Write("{0} ", number);
                }
                Console.WriteLine();
            }
            
            List<int> results = CommonManyIntervals(vectors);
            Console.Write("Results: ");
            foreach (int result in results)
            {
                Console.Write("{0} ", result);
            }
            Console.WriteLine();
        }
        
        public const int MAX_VALUE = 30;
        public const int MAX_LENGTH = 10;
    }
}
Размещено в C#
Просмотров 124 Комментарии 0
Всего комментариев 0
Комментарии
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.